1728. 猫和老鼠游戏 II

Hard

题目描述

由一只猫和一只老鼠玩一个游戏。

环境由一个 rows x cols 的网格表示，其中每个元素是墙、地板、玩家（猫、老鼠）或食物。

玩家由字符 'C'（猫）、'M'（老鼠）表示。
地板由字符 '.' 表示，可以行走。
墙由字符 '#' 表示，不能行走。
食物由字符 'F' 表示，可以行走。
网格中只有一个 'C'、'M' 和 'F' 字符。

老鼠和猫按照以下规则进行游戏：

老鼠先移动，然后它们轮流移动。
在每一轮中，猫和老鼠可以跳到四个方向之一（左、右、上、下）。它们不能跳过墙或跳到网格外面。
catJump 和 mouseJump 分别是猫和老鼠一次能跳的最大长度。猫和老鼠可以跳比最大长度短的距离。
允许停留在同一位置。
老鼠可以跳过猫。

游戏可以通过 4 种方式结束：

如果猫占据与老鼠相同的位置，猫获胜。
如果猫先到达食物，猫获胜。
如果老鼠先到达食物，老鼠获胜。
如果老鼠在 1000 轮内无法到达食物，猫获胜。

给定一个 rows x cols 矩阵 grid 和两个整数 catJump 和 mouseJump，如果老鼠在双方都发挥最优策略的情况下能获胜，则返回 true，否则返回 false。

示例 1：

输入：grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
输出：true
解释：猫无法在其回合中抓住老鼠，也无法在老鼠之前到达食物。

示例 2：

输入：grid = ["M.C...F"], catJump = 1, mouseJump = 4
输出：true

示例 3：

输入：grid = ["M.C...F"], catJump = 1, mouseJump = 3
输出：false

约束条件：

rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] 仅包含字符 'C'、'M'、'F'、'.' 和 '#'。
网格中只有一个 'C'、'M' 和 'F' 字符。
1 <= catJump, mouseJump <= 8

解题思路

这是一个经典的博弈论问题，可以用动态规划结合极小极大算法（Minimax）来解决。

核心思路：

状态定义：用 (mouseRow, mouseCol, catRow, catCol, turn, moves) 表示游戏状态，其中 turn 表示轮到谁（0为老鼠，1为猫），moves 表示已进行的回合数。
终止条件：
- 老鼠到达食物：老鼠获胜
- 猫到达食物或猫抓到老鼠：猫获胜
- 超过1000回合：猫获胜
状态转移：
- 老鼠回合：老鼠选择最优移动，只要有一个移动能获胜就返回true
- 猫回合：猫选择最优移动，所有移动都必须让老鼠败北才返回false
记忆化搜索：使用哈希表缓存已计算的状态，避免重复计算。
移动生成：对于每个玩家，枚举四个方向和所有可能的跳跃距离（包括原地不动）。

优化要点：

由于网格最大8x8，状态空间相对较小，记忆化搜索很有效
限制最大回合数防止无限循环
预处理找到猫、老鼠和食物的初始位置

代码实现

class Solution {
public:
    int rows, cols, foodRow, foodCol;
    vector<vector<int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    map<vector<int>, int> memo;
    
    bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
        rows = grid.size();
        cols = grid[0].size();
        
        int mouseRow = -1, mouseCol = -1, catRow = -1, catCol = -1;
        
        // 找到初始位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 'M') {
                    mouseRow = i; mouseCol = j;
                } else if (grid[i][j] == 'C') {
                    catRow = i; catCol = j;
                } else if (grid[i][j] == 'F') {
                    foodRow = i; foodCol = j;
                }
            }
        }
        
        return canMouseWinHelper(grid, mouseRow, mouseCol, catRow, catCol, 0, 0, mouseJump, catJump) == 1;
    }
    
    int canMouseWinHelper(vector<string>& grid, int mouseRow, int mouseCol, int catRow, int catCol, 
                         int turn, int moves, int mouseJump, int catJump) {
        if (moves >= 1000) return 2; // 猫获胜
        if (mouseRow == foodRow && mouseCol == foodCol) return 1; // 老鼠获胜
        if (catRow == foodRow && catCol == foodCol) return 2; // 猫获胜
        if (mouseRow == catRow && mouseCol == catCol) return 2; // 猫获胜
        
        vector<int> key = {mouseRow, mouseCol, catRow, catCol, turn, moves};
        if (memo.count(key)) return memo[key];
        
        if (turn == 0) { // 老鼠回合
            bool canWin = false;
            // 尝试所有可能的移动
            for (auto& dir : directions) {
                for (int jump = 0; jump <= mouseJump; jump++) {
                    int newRow = mouseRow + dir[0] * jump;
                    int newCol = mouseCol + dir[1] * jump;
                    if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || 
                        grid[newRow][newCol] == '#') break;
                    
                    if (canMouseWinHelper(grid, newRow, newCol, catRow, catCol, 1, moves + 1, mouseJump, catJump) == 1) {
                        canWin = true;
                        break;
                    }
                }
                if (canWin) break;
            }
            memo[key] = canWin ? 1 : 2;
        } else { // 猫回合
            bool allLose = true;
            for (auto& dir : directions) {
                for (int jump = 0; jump <= catJump; jump++) {
                    int newRow = catRow + dir[0] * jump;
                    int newCol = catCol + dir[1] * jump;
                    if (newRow < 0 || newRow >= rows || newCol < 0 || newCol >= cols || 
                        grid[newRow][newCol] == '#') break;
                    
                    if (canMouseWinHelper(grid, mouseRow, mouseCol, newRow, newCol, 0, moves + 1, mouseJump, catJump) != 1) {
                        allLose = false;
                        break;
                    }
                }
                if (!allLose) break;
            }
            memo[key] = allLose ? 1 : 2;
        }
        
        return memo[key];
    }
};

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        rows, cols = len(grid), len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        # 找到初始位置
        mouse_pos = cat_pos = food_pos = None
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 'M':
                    mouse_pos = (i, j)
                elif grid[i][j] == 'C':
                    cat_pos = (i, j)
                elif grid[i][j] == 'F':
                    food_pos = (i, j)
        
        memo = {}
        
        def dfs(mouse_row, mouse_col, cat_row, cat_col, turn, moves):
            if moves >= 1000:
                return False  # 猫获胜
            if (mouse_row, mouse_col) == food_pos:
                return True   # 老鼠获胜
            if (cat_row, cat_col) == food_pos or (mouse_row, mouse_col) == (cat_row, cat_col):
                return False  # 猫获胜
            
            key = (mouse_row, mouse_col, cat_row, cat_col, turn, moves)
            if key in memo:
                return memo[key]
            
            if turn == 0:  # 老鼠回合
                can_win = False
                for dx, dy in directions:
                    for jump in range(mouseJump + 1):
                        new_row = mouse_row + dx * jump
                        new_col = mouse_col + dy * jump
                        if (new_row < 0 or new_row >= rows or new_col < 0 or 
                            new_col >= cols or grid[new_row][new_col] == '#'):
                            break
                        
                        if dfs(new_row, new_col, cat_row, cat_col, 1, moves + 1):
                            can_win = True
                            break
                    if can_win:
                        break
                memo[key] = can_win
            else:  # 猫回合
                all_lose = True
                for dx, dy in directions:
                    for jump in range(catJump + 1):
                        new_row = cat_row + dx * jump
                        new_col = cat_col + dy * jump
                        if (new_row < 0 or new_row >= rows or new_col < 0 or 
                            new_col >= cols or grid[new_row][new_col] == '#'):
                            break
                        
                        if not dfs(mouse_row, mouse_col, new_row, new_col, 0, moves + 1):
                            all_lose = False
                            break
                    if not all_lose:
                        break
                memo[key] = all_lose
            
            return memo[key]
        
        return dfs(mouse_pos[0], mouse_pos[1], cat_pos[0], cat_pos[1], 0, 0)

public class Solution {
    private int rows, cols;
    private int[,] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    private Dictionary<string, int> memo = new Dictionary<string, int>();
    private int foodRow, foodCol;
    
    public bool CanMouseWin(string[] grid, int catJump, int mouseJump) {
        rows = grid.Length;
        cols = grid[0].Length;
        
        int mouseRow = -1, mouseCol = -1, catRow = -1, catCol = -1;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 'M') {
                    mouseRow = i; mouseCol = j;
                } else if (grid[i][j] == 'C') {
                    catRow = i; catCol = j;
                } else if (grid[i][j] == 'F') {
                    foodRow = i; foodCol = j;
                }
            }
        }
        
        return Dfs(grid, mouseRow, mouseCol, catRow, catCol, 0, 0, mouseJump, catJump) == 1;
    }
    
    private int Dfs(string[] grid, int mouseRow, int mouseCol, int catRow, int catCol, 
                   int turn, int moves, int mouseJump, int catJump) {
        if (moves >= 1000) return 2;
        if (mouseRow == foodRow && mouseCol == foodCol) return 1;
        if (catRow == foodRow && catCol == foodCol) return 2;
        if (mouseRow == catRow && mouseCol == catCol) return 2;
        
        string key = $"{mouseRow},{mouseCol},{catRow},{catCol},{turn},{moves}";
        if (memo.ContainsKey(key)) return memo[key];
        
        if (turn == 0) {
            bool canWin = false;
            for (int d = 0; d < 4; d++) {
                for (int jump = 0; jump <= mouseJump; jump++) {
                    int newRow = mouseRow + directions[d,0] * jump;
                    int newCol = mouseCol + directions[d,1] * jump;
                    if (newRow < 0 || newRow >= rows || newCol < 0 || 
                        newCol >= cols || grid[newRow][newCol] == '#') break;
                    
                    if (Dfs(grid, newRow, newCol, catRow, catCol, 1, moves + 1, mouseJump, catJump) == 1) {
                        canWin = true;
                        break;
                    }
                }
                if (canWin) break;
            }
            memo[key] = canWin ? 1 : 2;
        } else {
            bool allLose = true;
            for (int d = 0; d < 4; d++) {
                for (int jump = 0; jump <= catJump; jump++) {
                    int newRow = catRow + directions[d,0] * jump;
                    int newCol = catCol + directions[d,1] * jump;
                    if (newRow < 0 || newRow >= rows || newCol < 0 || 
                        newCol >= cols || grid[newRow][newCol] == '#') break;
                    
                    if (Dfs(grid, mouseRow, mouseCol, newRow, newCol, 0, moves + 1, mouseJump, catJump) != 1) {
                        allLose = false;
                        break;
                    }
                }
                if (!allLose) break;
            }
            memo[key] = allLose ? 1 : 2;
        }
        
        return memo[key];
    }
}

var canMouseWin = function(grid, catJump, mouseJump) {
    const rows = grid.length;
    const cols = grid[0].length;
    let mousePos, catPos, foodPos;
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (grid[i][j] === 'M') mousePos = [i, j];
            else if (grid[i][j] === 'C') catPos = [i, j];
            else if (grid[i][j] === 'F') foodPos = [i, j];
        }
    }
    
    const memo = new Map();
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    function getKey(mouseR, mouseC, catR, catC, turn) {
        return `${mouseR},${mouseC},${catR},${catC},${turn}`;
    }
    
    function getPossibleMoves(r, c, maxJump) {
        const moves = [[r, c]]; // can stay in place
        for (const [dr, dc] of directions) {
            for (let step = 1; step <= maxJump; step++) {
                const nr = r + dr * step;
                const nc = c + dc * step;
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === '#') {
                    break;
                }
                moves.push([nr, nc]);
            }
        }
        return moves;
    }
    
    function dfs(mouseR, mouseC, catR, catC, turn) {
        if (turn >= 2000) return false; // Too many turns, cat wins
        if (mouseR === catR && mouseC === catC) return false; // Cat caught mouse
        if (catR === foodPos[0] && catC === foodPos[1]) return false; // Cat reached food
        if (mouseR === foodPos[0] && mouseC === foodPos[1]) return true; // Mouse reached food
        
        const key = getKey(mouseR, mouseC, catR, catC, turn);
        if (memo.has(key)) return memo.get(key);
        
        let result;
        
        if (turn % 2 === 0) { // Mouse's turn
            result = false;
            const mouseMoves = getPossibleMoves(mouseR, mouseC, mouseJump);
            for (const [newMouseR, newMouseC] of mouseMoves) {
                if (dfs(newMouseR, newMouseC, catR, catC, turn + 1)) {
                    result = true;
                    break;
                }
            }
        } else { // Cat's turn
            result = true;
            const catMoves = getPossibleMoves(catR, catC, catJump);
            for (const [newCatR, newCatC] of catMoves) {
                if (!dfs(mouseR, mouseC, newCatR, newCatC, turn + 1)) {
                    result = false;
                    break;
                }
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dfs(mousePos[0], mousePos[1], catPos[0], catPos[1], 0);
};

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

复杂度分析

复杂度类型	复杂度分析
时间复杂度	O(R²C²×T×(mouseJump+catJump)) 其中R×C是网格大小，T是最大回合数(1000)
空间复杂度	O(R²C²×T) 记忆化存储的状态数量

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目