You are given two integers, m and n, representing the number of rows and columns of a grid. Each cell of the grid can be painted using one of three different colors. The grid must be painted such that:
10^9 + 7.
Constraints:
1 <= m <= 51 <= n <= 1000
The problem requires finding all valid colorings for a grid of size m x n such that no two adjacent cells (either horizontally or vertically) share the same color. The answer can be large, so return it modulo 10^9 + 7.
At first glance, it may seem feasible to try every possible coloring of the grid and count those that satisfy the constraints. However, for large values of n, this brute-force approach is computationally infeasible.
Let's examine the constraints:
The key insight is to:
Let's break down the solution step by step:
m, generate all possible colorings where no two adjacent cells are the same color.m=3, (1,2,3)).dp[col][pattern] be the number of ways to color up to column col with the last row coloring being pattern.dp[0][pattern] to 1 for all valid row colorings.dp[col][curr] by summing over all compatible previous row colorings.dp[n-1][pattern] for all patterns to get the total number of ways.
We use a hash map or dictionary to store DP states, as the number of valid row colorings is manageable (since m <= 5).
Let's consider m = 2 and n = 3 (a 2x3 grid).
For this example, the result would be 54.
Brute-force approach:
3^{m \times n}n.P be the number of valid row colorings (for m=5, P is at most a few hundred).n columns, we process all P patterns, and for each pattern, all compatible patterns (also up to P).O(n \times P^2), but P is small for m \leq 5.O(P) (since we only need to store current and previous DP states).This is efficient and feasible for the given constraints.
The key to solving the "Painting a Grid With Three Different Colors" problem is recognizing that we can break the coloring process into row-by-row states, and use dynamic programming to efficiently count all valid configurations. By precomputing valid row patterns and their compatibilities, and iteratively updating the number of ways for each column, we avoid brute-force enumeration. This approach leverages the small grid height (m) and is fast even for large n. The elegance comes from reducing a seemingly complex 2D problem into manageable 1D DP states.
MOD = 10**9 + 7
def colorTheGrid(m, n):
from itertools import product, combinations
# Generate all valid row colorings
def valid_rows(m):
def backtrack(pos, curr):
if pos == m:
res.append(tuple(curr))
return
for color in (0,1,2):
if pos == 0 or curr[-1] != color:
curr.append(color)
backtrack(pos+1, curr)
curr.pop()
res = []
backtrack(0, [])
return res
valid = valid_rows(m)
idx_map = {row: i for i, row in enumerate(valid)}
P = len(valid)
# Build compatibility
compat = [[] for _ in range(P)]
for i, a in enumerate(valid):
for j, b in enumerate(valid):
if all(x != y for x, y in zip(a, b)):
compat[i].append(j)
dp = [1] * P
for _ in range(n-1):
ndp = [0] * P
for i in range(P):
for j in compat[i]:
ndp[j] = (ndp[j] + dp[i]) % MOD
dp = ndp
return sum(dp) % MOD
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int colorTheGrid(int m, int n) {
const int MOD = 1e9 + 7;
vector<vector<int>> patterns;
vector<int> curr;
function<void(int)> backtrack = [&](int pos) {
if (pos == m) {
patterns.push_back(curr);
return;
}
for (int c = 0; c < 3; ++c) {
if (pos == 0 || curr.back() != c) {
curr.push_back(c);
backtrack(pos+1);
curr.pop_back();
}
}
};
for (int c = 0; c < 3; ++c) {
curr.push_back(c);
backtrack(1);
curr.pop_back();
}
int P = patterns.size();
vector<vector<int>> compat(P);
for (int i = 0; i < P; ++i) {
for (int j = 0; j < P; ++j) {
bool ok = true;
for (int k = 0; k < m; ++k) {
if (patterns[i][k] == patterns[j][k]) {
ok = false;
break;
}
}
if (ok) compat[i].push_back(j);
}
}
vector<int> dp(P, 1);
for (int col = 1; col < n; ++col) {
vector<int> ndp(P, 0);
for (int i = 0; i < P; ++i) {
for (int j : compat[i]) {
ndp[j] = (ndp[j] + dp[i]) % MOD;
}
}
dp = ndp;
}
int res = 0;
for (int x : dp) res = (res + x) % MOD;
return res;
}
};
import java.util.*;
class Solution {
static final int MOD = 1000000007;
public int colorTheGrid(int m, int n) {
List<int[]> patterns = new ArrayList<>();
backtrack(m, 0, new int[m], patterns);
int P = patterns.size();
List<List<Integer>> compat = new ArrayList<>();
for (int i = 0; i < P; ++i) compat.add(new ArrayList<>());
for (int i = 0; i < P; ++i) {
for (int j = 0; j < P; ++j) {
boolean ok = true;
for (int k = 0; k < m; ++k) {
if (patterns.get(i)[k] == patterns.get(j)[k]) {
ok = false;
break;
}
}
if (ok) compat.get(i).add(j);
}
}
int[] dp = new int[P];
Arrays.fill(dp, 1);
for (int col = 1; col < n; ++col) {
int[] ndp = new int[P];
for (int i = 0; i < P; ++i) {
for (int j : compat.get(i)) {
ndp[j] = (ndp[j] + dp[i]) % MOD;
}
}
dp = ndp;
}
int res = 0;
for (int x : dp) res = (res + x) % MOD;
return res;
}
private void backtrack(int m, int pos, int[] curr, List<int[]> patterns) {
if (pos == m) {
patterns.add(curr.clone());
return;
}
for (int c = 0; c < 3; ++c) {
if (pos == 0 || curr[pos-1] != c) {
curr[pos] = c;
backtrack(m, pos+1, curr, patterns);
}
}
}
}
var colorTheGrid = function(m, n) {
const MOD = 1e9 + 7;
let patterns = [];
function backtrack(pos, curr) {
if (pos === m) {
patterns.push(curr.slice());
return;
}
for (let c = 0; c < 3; ++c) {
if (pos === 0 || curr[pos-1] !== c) {
curr.push(c);
backtrack(pos+1, curr);
curr.pop();
}
}
}
backtrack(0, []);
let P = patterns.length;
let compat = Array.from({length: P}, () => []);
for (let i = 0; i < P; ++i) {
for (let j = 0; j < P; ++j) {
let ok = true;
for (let k = 0; k < m; ++k) {
if (patterns[i][k] === patterns[j][k]) {
ok = false;
break;
}
}
if (ok) compat[i].push(j);
}
}
let dp = Array(P).fill(1);
for (let col = 1; col < n; ++col) {
let ndp = Array(P).fill(0);
for (let i = 0; i < P; ++i) {
for (let j of compat[i]) {
ndp[j] = (ndp[j] + dp[i]) % MOD;
}
}
dp = ndp;
}
return dp.reduce((a, b) => (a + b) % MOD, 0);
};