Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1931.html

1931. Painting a Grid With Three Different Colors

Level

Hard

Description

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 10^9 + 7.

Example 1:

Image text

Input: m = 1, n = 1

Output: 3

Explanation: The three possible colorings are shown in the image above.

Example 2:

Image text

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

Constraints:

  • 1 <= m <= 5
  • 1 <= n <= 1000

Solution

There are m rows and n columns. For each column, precalculate all legal states such that no two adjacent cells have the same color, and precalculate all pairs of column states that can be two adjacent columns. Then for each column, calculate the number of ways to paint all columns up to the column. Finally, return the number of ways to paint all n columns.

  • class Solution {
    public int colorTheGrid(int m, int n) {
        final int MODULO = 1000000007;
        List<Integer> types = new ArrayList<Integer>();
        int maxCount = (int) Math.pow(3, m);
        for (int i = 0; i < maxCount; i++) {
            if (adjacentDistinct(i, m))
                types.add(i);
        }
        int typeCnt = types.size();
        int[][] related = new int[typeCnt][typeCnt];
        for (int i = 0; i < typeCnt; i++) {
            int type1 = types.get(i);
            int[] arr1 = new int[m];
            for (int k = m - 1; k >= 0 && type1 > 0; k--) {
                arr1[k] = type1 % 3;
                type1 /= 3;
            }
            for (int j = 0; j < typeCnt; j++) {
                int type2 = types.get(j);
                int[] arr2 = new int[m];
                for (int k = m - 1; k >= 0 && type2 > 0; k--) {
                    arr2[k] = type2 % 3;
                    type2 /= 3;
                }
                boolean flag = true;
                for (int k = 0; k < m; k++) {
                    if (arr1[k] == arr2[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    related[i][j] = 1;
            }
        }
        int[][] f = new int[n + 1][typeCnt];
        for (int i = 0; i < typeCnt; i++)
            f[1][i] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < typeCnt; j++) {
                for (int k = 0; k < typeCnt; k++) {
                    if (related[k][j] != 0)
                        f[i][j] = (f[i][j] + f[i - 1][k]) % MODULO;
                }
            }
        }
        int count = 0;
        for (int j = 0; j < typeCnt; j++)
            count = (count + f[n][j]) % MODULO;
        return count;
    }

    public boolean adjacentDistinct(int num, int m) {
        int prev = -1;
        for (int i = 0; i < m; i++) {
            int curr = num % 3;
            if (curr == prev)
                return false;
            prev = curr;
            num /= 3;
        }
        return true;
    }
}

  • // OJ: https://leetcode.com/problems/painting-a-grid-with-three-different-colors/
// Time: O(V^2 * M + VNM) where V is the count of valid column vectors
// Space: O(V^2)
class Solution {
    vector<unordered_map<int, long>> dp;
    long mod = 1e9 + 7;
    vector<string> states;
    vector<vector<int>> G;
    void getStates(int len, int prev, string &s) {
        if (s.size() == len) {
            states.push_back(s);
            return;
        }
        for (int j = 0; j < 3; ++j) {
            if (prev == j) continue;
            s += '0' + j;
            getStates(len, j, s);
            s.pop_back();
        }
    }
    bool areNeighbors(string &a, string &b) {
        for (int i = 0; i < a.size(); ++i)  {
            if (a[i] == b[i]) return false;
        }
        return true;
    }
    long dfs(int len, int u) {
        if (len == 1) return 1;
        if (dp[len].count(u)) return dp[len][u];
        long ans = 0;
        for (int v : G[u]) {
            ans = (ans + dfs(v, len - 1)) % mod;
        }
        return dp[len][u] = ans;
    }
public:
    int colorTheGrid(int m, int n) {
        string s;
        getStates(m, -1, s);
        int N = states.size();
        G.assign(N, {});
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (areNeighbors(states[i], states[j])) {
                    G[i].push_back(j);
                }
            }
        }
        long ans = 0;
        dp.assign(n + 1, {});
        for (int i = 0; i < N; ++i) ans = (ans + dfs(n, i)) % mod;
        return ans;
    }
};

  • print("Todo!")

All Problems

All Solutions