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

Hard

题目描述

给你两个整数 m 和 n。考虑一个 m x n 的网格，其中每个单元格最初都是白色的。你可以将每个单元格涂成红色、绿色或蓝色。所有单元格都必须被涂色。

返回为网格涂色的方案数，使得没有两个相邻的单元格具有相同的颜色。由于答案可能非常大，请返回对 10^9 + 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

提示：

用基于每个单元格颜色的位掩码表示每个彩色列。
使用状态为 (currentCell, prevColumn) 的位掩码动态规划。

解题思路

这是一个经典的状态压缩动态规划问题。由于 m <= 5，我们可以用状态压缩的方式来表示每一列的涂色状态。

核心思路：

状态表示：由于每个格子有3种颜色（0,1,2），我们可以用三进制数来表示一列的涂色状态。例如，对于 m=3 的列，状态 012 表示从上到下分别涂成颜色0、1、2。
状态转移：使用动态规划，dp[i][state] 表示第 i 列处于 state 状态时的方案数。状态转移需要满足：
- 当前列内部相邻格子颜色不同
- 当前列与前一列对应位置的格子颜色不同
预处理优化：
- 预先生成所有有效的列状态（列内部无相邻相同颜色）
- 预先计算相邻列之间的兼容关系
算法流程：
- 生成所有合法的单列状态
- 建立相邻列的兼容关系映射
- 初始化第一列的dp值
- 逐列进行状态转移
- 累加最后一列所有状态的方案数

时间复杂度主要取决于有效状态数量，由于 m <= 5，状态数量最多为 3^5 = 243，实际有效状态更少。

代码实现

class Solution {
public:
    int colorTheGrid(int m, int n) {
        const int MOD = 1e9 + 7;
        
        // 生成所有有效的列状态
        vector<int> validStates;
        function<void(int, int, int)> generateStates = [&](int pos, int state, int prev) {
            if (pos == m) {
                validStates.push_back(state);
                return;
            }
            for (int color = 0; color < 3; color++) {
                if (color != prev) {
                    generateStates(pos + 1, state * 3 + color, color);
                }
            }
        };
        generateStates(0, 0, -1);
        
        // 预计算相邻状态的兼容性
        int stateCount = validStates.size();
        vector<vector<int>> compatible(stateCount);
        
        auto getColors = [&](int state, int m) {
            vector<int> colors(m);
            for (int i = m - 1; i >= 0; i--) {
                colors[i] = state % 3;
                state /= 3;
            }
            return colors;
        };
        
        for (int i = 0; i < stateCount; i++) {
            vector<int> colors1 = getColors(validStates[i], m);
            for (int j = 0; j < stateCount; j++) {
                vector<int> colors2 = getColors(validStates[j], m);
                bool isCompatible = true;
                for (int k = 0; k < m; k++) {
                    if (colors1[k] == colors2[k]) {
                        isCompatible = false;
                        break;
                    }
                }
                if (isCompatible) {
                    compatible[i].push_back(j);
                }
            }
        }
        
        // 动态规划
        vector<long long> dp(stateCount, 1);
        
        for (int col = 1; col < n; col++) {
            vector<long long> newDp(stateCount, 0);
            for (int curr = 0; curr < stateCount; curr++) {
                for (int prev : compatible[curr]) {
                    newDp[curr] = (newDp[curr] + dp[prev]) % MOD;
                }
            }
            dp = newDp;
        }
        
        long long result = 0;
        for (int state = 0; state < stateCount; state++) {
            result = (result + dp[state]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def colorTheGrid(self, m: int, n: int) -> int:
        MOD = 10**9 + 7
        
        # 生成所有有效的列状态
        valid_states = []
        
        def generate_states(pos, state, prev):
            if pos == m:
                valid_states.append(state)
                return
            for color in range(3):
                if color != prev:
                    generate_states(pos + 1, state * 3 + color, color)
        
        generate_states(0, 0, -1)
        
        # 预计算相邻状态的兼容性
        def get_colors(state, m):
            colors = []
            for _ in range(m):
                colors.append(state % 3)
                state //= 3
            return colors[::-1]
        
        state_count = len(valid_states)
        compatible = [[] for _ in range(state_count)]
        
        for i in range(state_count):
            colors1 = get_colors(valid_states[i], m)
            for j in range(state_count):
                colors2 = get_colors(valid_states[j], m)
                if all(c1 != c2 for c1, c2 in zip(colors1, colors2)):
                    compatible[i].append(j)
        
        # 动态规划
        dp = [1] * state_count
        
        for col in range(1, n):
            new_dp = [0] * state_count
            for curr in range(state_count):
                for prev in compatible[curr]:
                    new_dp[curr] = (new_dp[curr] + dp[prev]) % MOD
            dp = new_dp
        
        return sum(dp) % MOD

public class Solution {
    public int ColorTheGrid(int m, int n) {
        const int MOD = 1000000007;
        
        // 生成所有有效的列状态
        List<int> validStates = new List<int>();
        
        void GenerateStates(int pos, int state, int prev) {
            if (pos == m) {
                validStates.Add(state);
                return;
            }
            for (int color = 0; color < 3; color++) {
                if (color != prev) {
                    GenerateStates(pos + 1, state * 3 + color, color);
                }
            }
        }
        
        GenerateStates(0, 0, -1);
        
        // 预计算相邻状态的兼容性
        int[] GetColors(int state, int m) {
            int[] colors = new int[m];
            for (int i = m - 1; i >= 0; i--) {
                colors[i] = state % 3;
                state /= 3;
            }
            return colors;
        }
        
        int stateCount = validStates.Count;
        List<int>[] compatible = new List<int>[stateCount];
        for (int i = 0; i < stateCount; i++) {
            compatible[i] = new List<int>();
        }
        
        for (int i = 0; i < stateCount; i++) {
            int[] colors1 = GetColors(validStates[i], m);
            for (int j = 0; j < stateCount; j++) {
                int[] colors2 = GetColors(validStates[j], m);
                bool isCompatible = true;
                for (int k = 0; k < m; k++) {
                    if (colors1[k] == colors2[k]) {
                        isCompatible = false;
                        break;
                    }
                }
                if (isCompatible) {
                    compatible[i].Add(j);
                }
            }
        }
        
        // 动态规划
        long[] dp = new long[stateCount];
        for (int i = 0; i < stateCount; i++) {
            dp[i] = 1;
        }
        
        for (int col = 1; col < n; col++) {
            long[] newDp = new long[stateCount];
            for (int curr = 0; curr < stateCount; curr++) {
                foreach (int prev in compatible[curr]) {
                    newDp[curr] = (newDp[curr] + dp[prev]) % MOD;
                }
            }
            dp = newDp;
        }
        
        long result = 0;
        for (int state = 0; state < stateCount; state++) {
            result = (result + dp[state]) % MOD;
        }
        
        return (int)result;
    }
}

var colorTheGrid = function(m, n) {
    const MOD = 1000000007;
    
    // Generate all valid colorings for a single column
    function generateValidColumns(m) {
        const validColumns = [];
        
        function backtrack(col, colors) {
            if (colors.length === m) {
                validColumns.push([...colors]);
                return;
            }
            
            for (let color = 0; color < 3; color++) {
                if (colors.length === 0 || colors[colors.length - 1] !== color) {
                    colors.push(color);
                    backtrack(col, colors);
                    colors.pop();
                }
            }
        }
        
        backtrack(0, []);
        return validColumns;
    }
    
    // Check if two columns can be adjacent
    function canBeAdjacent(col1, col2) {
        for (let i = 0; i < m; i++) {
            if (col1[i] === col2[i]) {
                return false;
            }
        }
        return true;
    }
    
    const validColumns = generateValidColumns(m);
    const numValidColumns = validColumns.length;
    
    // Build adjacency list
    const adjacent = Array(numValidColumns).fill(null).map(() => []);
    for (let i = 0; i < numValidColumns; i++) {
        for (let j = 0; j < numValidColumns; j++) {
            if (canBeAdjacent(validColumns[i], validColumns[j])) {
                adjacent[i].push(j);
            }
        }
    }
    
    // DP: dp[i] = number of ways to color columns ending with column i
    let dp = Array(numValidColumns).fill(1);
    
    for (let col = 1; col < n; col++) {
        const newDp = Array(numValidColumns).fill(0);
        
        for (let i = 0; i < numValidColumns; i++) {
            for (let j of adjacent[i]) {
                newDp[j] = (newDp[j] + dp[i]) % MOD;
            }
        }
        
        dp = newDp;
    }
    
    return dp.reduce((sum, val) => (sum + val) % MOD, 0);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(S² × n)，其中 S 是有效状态数量（最多 3^m，实际更少），n 为列数
空间复杂度	O(S²)，用于存储状态兼容性关系和 DP 数组

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目