You are given two integers m and n. Consider an m x n grid where each cell is initially…
- User
You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.
Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.
Example 1:
Input: m = 1, n = 1 Output: 3 Explanation: The three possible colorings are shown in the image above.
Example 2:
Input: m = 1, n = 2 Output: 6 Explanation: The six possible colorings are shown in the image above.
Example 3:
Input: m = 5, n = 5 Output: 580986
- Assistant
Here’s a clean way to think about (and implement) the solution in O(n·S²·m) time, where
S = “number of valid column‐colorings” = at most 3ᵐ:-
Fix the smaller dimension to be “rows” (m) and the larger to be “columns” (n).
If n < m, swap them. -
Encode each column‐pattern as a base-3 integer mask in [0, 3ᵐ).
The i-th trit (0,1,2) is the color of row i. -
Precompute all “valid” masks (no two vertically adjacent cells are same):
valid_masks = [mask ∈ [0,3ᵐ) | for all i< m–1, trit_i(mask) ≠ trit_{i+1}(mask)]. -
Precompute a compatibility list:
comp[mask₁] = [mask₂ ∈ valid_masks | for all rows i, trit_i(mask₁) ≠ trit_i(mask₂)]. -
DP over columns: dp[j][mask] = #ways to color the first j columns ending in pattern=mask.
Base: dp[1][mask] = 1 for all valid_masks.
Transition:
dp[j][mask₂] = Σₘₐₛₖ₁∈comp[mask₂] dp[j–1][mask₁] (mod 10⁹+7)Answer = Σₘₐₛₖ dp[n][mask].
Since you only need the previous column to compute the next, you can roll the DP into two arrays of size |valid_masks|.
def numWays(m: int, n: int) -> int: MOD = 10**9 + 7 # Always let m be the smaller dimension (rows) if m > n: m, n = n, m # 1) Generate all valid column‐masks (no vertical repeats) max_mask = 3**m valid = [] trits = [[0]*m for _ in range(max_mask)] for mask in range(max_mask): x = mask ok = True for i in range(m): trits[mask][i] = x % 3 x //= 3 if i>0 and trits[mask][i] == trits[mask][i-1]: ok = False break if ok: valid.append(mask) # 2) Precompute compatibility: no horizontal repeats comp = {mask: [] for mask in valid} for a in valid: for b in valid: # check row-by-row for i in range(m): if trits[a][i] == trits[b][i]: break else: comp[a].append(b) # 3) DP over columns # dp_prev[a] = number of ways to end col j–1 with mask=a dp_prev = {mask: 1 for mask in valid} # j=1 for _ in range(2, n+1): dp_cur = {} for b in valid: total = 0 for a in comp[b]: total = (total + dp_prev[a]) % MOD dp_cur[b] = total dp_prev = dp_cur # 4) Sum over last column return sum(dp_prev.values()) % MOD # Examples print(numWays(1,1)) # 3 print(numWays(1,2)) # 6 print(numWays(5,5)) # 580986Explanation of the main ideas:
- We treat each column as a “state” (one of up to 3ᵐ colorings), but throw away any state with identical colors in adjacent rows.
- Two column‐states are “compatible” if they never use the same color in the same row (ensuring the no-adjacent-horizontal repeat rule).
- Then a straightforward 1D DP propagates these counts across the n columns in O(n·S·avg_deg) ≲ O(n·S²·m).
Since m ≤ n (we swap if not), the worst case is about m=5 → S≈120, so it runs blazingly fast for n up to even 10⁵ (≈10⁸ ops total).
-
- User
solve in js
- Assistant
Here’s a straightforward JavaScript implementation of the same column‐DP approach. It runs in roughly O(n·S²·m) where S = the number of “valid” column‐masks (≤3ᵐ). For m≤5 it’s very fast even up to large n.
/** * @param {number} m // rows * @param {number} n // cols * @return {number} // #ways mod 1e9+7 */ function numWays(m, n) { const MOD = 1e9 + 7; // Always let m <= n (so 3^m is as small as possible) if (m > n) [m, n] = [n, m]; // 1) Precompute 3^m and all trit‐representations const maxMask = 3 ** m; const trits = Array.from({ length: maxMask }, () => new Array(m)); for (let mask = 0; mask < maxMask; mask++) { let x = mask; for (let i = 0; i < m; i++) { trits[mask][i] = x % 3; x = Math.floor(x / 3); } } // 2) Collect "valid" masks (no two vertical neighbors are the same) const valid = []; for (let mask = 0; mask < maxMask; mask++) { let ok = true; for (let i = 1; i < m; i++) { if (trits[mask][i] === trits[mask][i - 1]) { ok = false; break; } } if (ok) valid.push(mask); } const S = valid.length; // 3) Build compatibility: comp[j] = array of i s.t. valid[i] can sit next to valid[j] const comp = Array.from({ length: S }, () => []); for (let j = 0; j < S; j++) { const mb = valid[j]; for (let i = 0; i < S; i++) { const ma = valid[i]; let ok = true; // Check row-by-row for horizontal adjacency for (let r = 0; r < m; r++) { if (trits[ma][r] === trits[mb][r]) { ok = false; break; } } if (ok) comp[j].push(i); } } // 4) DP over columns (rolling arrays) // dpPrev[i] = #ways to fill up to previous column ending in valid[i] let dpPrev = Array(S).fill(1); // base: first column can be any valid mask let dpCur = Array(S).fill(0); for (let col = 2; col <= n; col++) { dpCur.fill(0); for (let j = 0; j < S; j++) { // sum over all i compatible with j let sum = 0; for (let i of comp[j]) { sum = (sum + dpPrev[i]) % MOD; } dpCur[j] = sum; } [dpPrev, dpCur] = [dpCur, dpPrev]; } // 5) Sum up all ways for the last column return dpPrev.reduce((acc, v) => (acc + v) % MOD, 0); } // ===== Example runs ===== console.log(numWays(1, 1)); // 3 console.log(numWays(1, 2)); // 6 console.log(numWays(5, 5)); // 580986Explanation of steps:
- Swap so that
m ≤ n(keeps 3ᵐ small). - Encode each column‐pattern as a base-3 integer in
[0, 3ᵐ). - Filter out masks with vertical repeats.
- Precompute a compatibility list (
comp) so that two masks never have the same color in any row. - DP across columns:
dpPrev[i] = ways to color up to column j−1 ending in mask i
dpCur[j] = Σ(dpPrev[i]) over allicompatible withj - Answer = sum of dpPrev after n columns, modulo 1e9+7.
Feel free to tweak or ask if anything’s unclear! 😊
- Swap so that
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.