-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
100 lines (91 loc) · 2.3 KB
/
Solution.cs
File metadata and controls
100 lines (91 loc) · 2.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class Solution
{
int mod = (int)1e9 + 7;
Dictionary<int, List<int>> transitions = [];
List<int> validStates = [];
Dictionary<int, int[]> decodedStates = [];
// color: 0 - red, 1 - blue, 2 - green
public int ColorTheGrid(int m, int n)
{
GenerateValidStates(m);
GenerateTransitions(m);
Dictionary<int, int> dp = [];
foreach (int state in validStates)
{
dp[state] = 1;
}
for (int col = 1; col < n; col++)
{
Dictionary<int, int> next = [];
foreach (int curr in validStates)
{
long count = 0;
foreach (int prev in transitions[curr])
{
count = (count + dp[prev]) % mod;
}
next[curr] = (int)count;
}
dp = next;
}
long ret = 0;
foreach (int val in dp.Values)
{
ret = (ret + val) % mod;
}
return (int)ret;
}
void GenerateTransitions(int m)
{
foreach (var s1 in validStates)
{
transitions[s1] = [];
foreach (var s2 in validStates)
{
if (CanFollow(decodedStates[s1], decodedStates[s2]))
{
transitions[s1].Add(s2);
}
}
}
}
void GenerateValidStates(int m)
{
int total = (int)Math.Pow(3, m);
for (int mask = 0; mask < total; mask++)
{
int[] colors = Decode(mask, m);
if (IsValidColumn(colors))
{
validStates.Add(mask);
decodedStates[mask] = colors;
}
}
}
bool IsValidColumn(int[] colors)
{
for (int i = 1; i < colors.Length; i++)
{
if (colors[i] == colors[i - 1]) return false;
}
return true;
}
int[] Decode(int mask, int m)
{
int[] colors = new int[m];
for (int i = 0; i < m; i++)
{
colors[i] = mask % 3;
mask /= 3;
}
return colors;
}
bool CanFollow(int[] c1, int[] c2)
{
for (int i = 0; i < c1.Length; i++)
{
if (c1[i] == c2[i]) return false;
}
return true;
}
}