DSA problem
Painting a Grid With Three Different Colors
You are given two integers m and n. You must paint an m x n grid using three colors (call them R, G, B) such that no two adjacent cells (sharing a side) have the same color. Return the number of ways to do this, modulo 10^9 + 7.
The constraint m <= 5 is the central clue. A row is a length-m coloring with no two vertically-adjacent cells equal (the "internal" constraint). The number of such valid rows is small: at most 3 * 2^(m - 1) for m <= 5 — so 6, 12, 24, 48, or 96 valid rows. We can enumerate them once.
Then the problem becomes: count length-n sequences of valid rows where every consecutive pair of rows is "compatible," meaning every column j satisfies row[i][j] != row[i + 1][j] (the horizontal constraint between rows). For each row coloring, precompute the list of rows compatible with it. The DP is over columns of rows: dp[i][s] = sum of dp[i - 1][s'] over all s' compatible with s. The base case dp[0][s] = 1 for every valid s.
Encode each row as a base-3 integer of m digits to compare and store cheaply. Total complexity: O(R * R' * n) where R is the number of valid rows (<= 96) and R' is the average compatibility list size — well within limits for n <= 1000. Final answer: sum of dp[n - 1][s] over all valid s, modulo 10^9 + 7.
Examples
m = 1, n = 13m = 1, n = 26m = 5, n = 5580986Constraints
- 1 <= m <= 5
- 1 <= n <= 1000
- Use exactly three colors.
- No two adjacent cells (sharing a side) may share a color.
- Return the count modulo 10^9 + 7.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.