1931. 用三种不同颜色为网格涂色Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个整数 m 和 n 。构造一个 m x n 的网格，其中每个单元格最开始是白色。请你用红、绿、蓝三种颜色为每个单元格涂色。所有单元格都需要被涂色。

涂色方案需要满足：不存在相邻两个单元格颜色相同的情况。返回网格涂色的方法数。因为答案可能非常大，返回对 109 + 7 取余的结果。

示例 1：

输入：m = 1, n = 1
输出：3
解释：如上图所示，存在三种可能的涂色方案。

示例 2：

输入：m = 1, n = 2
输出：6
解释：如上图所示，存在六种可能的涂色方案。

示例 3：

输入：m = 5, n = 5
输出：580986

提示：

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

# 思路

三进制状态压缩dp

# 解法

class Solution {

    private int n;

    private boolean check(int x) {
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (x % 3 == last) {
                return false;
            }
            last = x % 3;
            x /= 3;
        }
        return true;
    }

    private boolean check(int x, int y) {
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();
        while (x > 0) {
            a.add(x % 3);
            x /= 3;
        }
        while (y > 0) {
            b.add(y % 3);
            y /= 3;
        }
        for (int i = 0; i < n; i++) {
            int v1 = 0, v2 = 0;
            if (i < a.size()) {
                v1 = a.get(i);
            }
            if (i < b.size()) {
                v2 = b.get(i);
            }
            if (v1 == v2) {
                return false;
            }
        }
        return true;
    }

    public int colorTheGrid(int n, int m) {
        this.n = n;
        int N = (int) Math.pow(3, n);
        int[][] dp = new int[m][N];
        for (int i = 0; i < N; i++) {
            if (check(i)) {
                dp[0][i] = 1;
            }
        }
        int mod = (int) 1e9 + 7;
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < N; j++) {
                if (check(j)) {
                    for (int k = 0; k < N; k++) {
                        if (check(k) && check(j, k)) {
                            dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
                        }
                    }
                }

            }
        }
        int res = 0;
        for (int i = 0; i < N; i++) {
            res = (res + dp[m - 1][i]) % mod;
        }
        return res;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java