golang 解法, 执行用时: 23 ms, 内存消耗: 9.2 MB, 提交时间: 2025-02-11 09:28:52
// 913. 猫和老鼠
func catMouseGame(gMouse, gCat [][]int, mouseStart, catStart, hole int) int {
n := len(gMouse)
deg := make([][][2]int, n)
for i := range deg {
deg[i] = make([][2]int, n)
}
for i, m := range gMouse {
for j, c := range gCat {
deg[i][j][0] = len(m)
deg[i][j][1] = len(c)
}
}
winner := make([][][2]int, n)
for i := range winner {
winner[i] = make([][2]int, n)
}
q := [][3]int{}
for i := range n {
winner[hole][i][1] = 1 // 鼠到达洞中（此时轮到猫移动），鼠获胜
winner[i][hole][0] = 2 // 猫到达洞中（此时轮到鼠移动），猫获胜
winner[i][i][0] = 2 // 猫和鼠出现在同一个节点，无论轮到谁移动，都是猫获胜
winner[i][i][1] = 2
q = append(q, [3]int{hole, i, 1})
q = append(q, [3]int{i, hole, 0})
q = append(q, [3]int{i, i, 0})
q = append(q, [3]int{i, i, 1})
}
// 获取 (mouse, cat, turn) 的上个状态（值尚未确定）
getPreStates := func(mouse, cat, turn int) (preStates [][2]int) {
if turn == 0 { // 当前轮到鼠移动
for _, preCat := range gCat[cat] { // 上一轮猫的位置
if winner[mouse][preCat][1] == 0 { // 猫无法移动到洞中
preStates = append(preStates, [2]int{mouse, preCat})
}
}
} else { // 当前轮到猫移动
for _, preMouse := range gMouse[mouse] { // 上一轮鼠的位置
if winner[preMouse][cat][0] == 0 {
preStates = append(preStates, [2]int{preMouse, cat})
}
}
}
return preStates
}
// 减少上个状态的度数
decDegToZero := func(preMouse, preCat, preTurn int) bool {
deg[preMouse][preCat][preTurn]--
return deg[preMouse][preCat][preTurn] == 0
}
for len(q) > 0 {
mouse, cat, turn := q[0][0], q[0][1], q[0][2]
q = q[1:]
win := winner[mouse][cat][turn] // 最终谁赢了
for _, pre := range getPreStates(mouse, cat, turn) {
preMouse, preCat, preTurn := pre[0], pre[1], turn^1
// 情况一：如果上一回合鼠从 pre 移动到 cur，最终鼠赢，那么标记 pre 状态的 winner = 鼠
// 情况二：如果上一回合猫从 pre 移动到 cur，最终猫赢，那么标记 pre 状态的 winner = 猫
// 情况三：如果上一回合鼠从 pre 移动到 cur，最终猫赢，那么待定，直到我们发现从 pre 出发能到达的状态都是猫赢，那么标记 pre 状态的 winner = 猫
// 情况四：如果上一回合猫从 pre 移动到 cur，最终鼠赢，那么待定，直到我们发现从 pre 出发能到达的状态都是鼠赢，那么标记 pre 状态的 winner = 鼠
if preTurn == win-1 || decDegToZero(preMouse, preCat, preTurn) {
winner[preMouse][preCat][preTurn] = win
q = append(q, [3]int{preMouse, preCat, preTurn}) // 继续倒推
}
}
}
// 鼠在节点 mouseStart，猫在节点 catStart，当前轮到鼠移动
return winner[mouseStart][catStart][0] // 返回最终谁赢了（或者平局）
}
func canMouseWin(grid []string, catJump, mouseJump int) bool {
dirs := [4]struct{ dx, dy int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}} // 左右上下
m, n := len(grid), len(grid[0])
// 鼠和猫分别建图
gMouse := make([][]int, m*n)
gCat := make([][]int, m*n)
var mx, my, cx, cy, fx, fy int
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == '#' { // 墙
continue
}
if grid[i][j] == 'M' { // 鼠的位置
mx, my = i, j
} else if grid[i][j] == 'C' { // 猫的位置
cx, cy = i, j
} else if grid[i][j] == 'F' { // 食物（洞）的位置
fx, fy = i, j
}
v := i*n + j // 二维坐标 (i,j) 映射为一维坐标 v
for _, d := range dirs { // 枚举左右上下四个方向
for k := range mouseJump + 1 { // 枚举跳跃长度
x, y := i+k*d.dx, j+k*d.dy
if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#' { // 出界或者遇到墙
break
}
gMouse[v] = append(gMouse[v], x*n+y) // 连边
}
for k := range catJump + 1 { // 枚举跳跃长度
x, y := i+k*d.dx, j+k*d.dy
if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#' { // 出界或者遇到墙
break
}
gCat[v] = append(gCat[v], x*n+y) // 连边
}
}
}
}
// 判断是否鼠赢
return catMouseGame(gMouse, gCat, mx*n+my, cx*n+cy, fx*n+fy) == 1
}
cpp 解法, 执行用时: 115 ms, 内存消耗: 44.6 MB, 提交时间: 2025-02-11 09:28:34
class Solution {
// 913. 猫和老鼠
int catMouseGame(vector<vector<int>>& g_mouse, vector<vector<int>>& g_cat, int mouse_start, int cat_start, int hole) {
int n = g_mouse.size();
vector deg(n, vector<array<int, 2>>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
deg[i][j][0] = g_mouse[i].size();
deg[i][j][1] = g_cat[j].size();
}
}
vector winner(n, vector<array<int, 2>>(n));
queue<tuple<int, int, int>> q;
for (int i = 0; i < n; i++) {
winner[hole][i][1] = 1; // 鼠到达洞中（此时轮到猫移动），鼠获胜
winner[i][hole][0] = 2; // 猫到达洞中（此时轮到鼠移动），猫获胜
winner[i][i][0] = winner[i][i][1] = 2; // 猫和鼠出现在同一个节点，无论轮到谁移动，都是猫获胜
q.emplace(hole, i, 1);
q.emplace(i, hole, 0);
q.emplace(i, i, 0);
q.emplace(i, i, 1);
}
// 获取 (mouse, cat, turn) 的上个状态（值尚未确定）
auto get_pre_states = [&](int mouse, int cat, int turn) {
vector<pair<int, int>> pre_states;
if (turn == 0) { // 当前轮到鼠移动
for (int pre_cat : g_cat[cat]) { // 上一轮猫的位置
if (winner[mouse][pre_cat][1] == 0) {
pre_states.emplace_back(mouse, pre_cat);
}
}
} else { // 当前轮到猫移动
for (int pre_mouse : g_mouse[mouse]) { // 上一轮鼠的位置
if (winner[pre_mouse][cat][0] == 0) {
pre_states.emplace_back(pre_mouse, cat);
}
}
}
return pre_states;
};
while (!q.empty()) {
auto [mouse, cat, turn] = q.front(); q.pop();
int win = winner[mouse][cat][turn]; // 最终谁赢了
int pre_turn = turn ^ 1;
for (auto [pre_mouse, pre_cat] : get_pre_states(mouse, cat, turn)) {
// 情况一：如果上一回合鼠从 pre 移动到 cur，最终鼠赢，那么标记 pre 状态的 winner = 鼠
// 情况二：如果上一回合猫从 pre 移动到 cur，最终猫赢，那么标记 pre 状态的 winner = 猫
// 情况三：如果上一回合鼠从 pre 移动到 cur，最终猫赢，那么待定，直到我们发现从 pre 出发能到达的状态都是猫赢，那么标记 pre 状态的 winner = 猫
// 情况四：如果上一回合猫从 pre 移动到 cur，最终鼠赢，那么待定，直到我们发现从 pre 出发能到达的状态都是鼠赢，那么标记 pre 状态的 winner = 鼠
if (pre_turn == win - 1 || --deg[pre_mouse][pre_cat][pre_turn] == 0) {
winner[pre_mouse][pre_cat][pre_turn] = win;
q.emplace(pre_mouse, pre_cat, pre_turn); // 继续倒推
}
}
}
// 鼠在节点 mouse_start，猫在节点 cat_start，当前轮到鼠移动
return winner[mouse_start][cat_start][0]; // 返回最终谁赢了（或者平局）
}
public:
bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
static constexpr int DIRS[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 左右上下
int m = grid.size(), n = grid[0].size();
// 鼠和猫分别建图
vector<vector<int>> g_mouse(m * n), g_cat(m * n);
int mx, my, cx, cy, fx, fy;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '#') { // 墙
continue;
}
if (grid[i][j] == 'M') { // 鼠的位置
mx = i; my = j;
} else if (grid[i][j] == 'C') { // 猫的位置
cx = i; cy = j;
} else if (grid[i][j] == 'F') { // 食物（洞）的位置
fx = i; fy = j;
}
int v = i * n + j; // 二维坐标 (i,j) 映射为一维坐标 v
for (auto [dx, dy] : DIRS) { // 枚举左右上下四个方向
for (int k = 0; k <= mouseJump; k++) { // 枚举跳跃长度
int x = i + k * dx, y = j + k * dy;
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') { // 出界或者遇到墙
break;
}
g_mouse[v].push_back(x * n + y); // 连边
}
for (int k = 0; k <= catJump; k++) { // 枚举跳跃长度
int x = i + k * dx, y = j + k * dy;
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') { // 出界或者遇到墙
break;
}
g_cat[v].push_back(x * n + y); // 连边
}
}
}
}
// 判断是否鼠赢
return catMouseGame(g_mouse, g_cat, mx * n + my, cx * n + cy, fx * n + fy) == 1;
}
};
java 解法, 执行用时: 46 ms, 内存消耗: 44.4 MB, 提交时间: 2025-02-11 09:28:14
class Solution {
private static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 左右上下
public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
int m = grid.length, n = grid[0].length();
// 鼠和猫分别建图
List<Integer>[] gMouse = new ArrayList[m * n];
List<Integer>[] gCat = new ArrayList[m * n];
Arrays.setAll(gMouse, i -> new ArrayList<>());
Arrays.setAll(gCat, i -> new ArrayList<>());
int mx = 0, my = 0, cx = 0, cy = 0, fx = 0, fy = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char c = grid[i].charAt(j);
if (c == '#') { // 墙
continue;
}
if (c == 'M') { // 鼠的位置
mx = i; my = j;
} else if (c == 'C') { // 猫的位置
cx = i; cy = j;
} else if (c == 'F') { // 食物（洞）的位置
fx = i; fy = j;
}
int v = i * n + j; // 二维坐标 (i,j) 映射为一维坐标 v
for (int[] dir : DIRS) { // 枚举左右上下四个方向
for (int k = 0; k <= mouseJump; k++) { // 枚举跳跃长度
int x = i + k * dir[0], y = j + k * dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x].charAt(y) == '#') { // 出界或者遇到墙
break;
}
gMouse[v].add(x * n + y); // 连边
}
for (int k = 0; k <= catJump; k++) { // 枚举跳跃长度
int x = i + k * dir[0], y = j + k * dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x].charAt(y) == '#') { // 出界或者遇到墙
break;
}
gCat[v].add(x * n + y); // 连边
}
}
}
}
// 判断是否鼠赢
return catMouseGame(gMouse, gCat, mx * n + my, cx * n + cy, fx * n + fy) == 1;
}
// 913. 猫和老鼠
private int catMouseGame(List<Integer>[] gMouse, List<Integer>[] gCat, int mouseStart, int catStart, int hole) {
int n = gMouse.length;
int[][][] deg = new int[n][n][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
deg[i][j][0] = gMouse[i].size();
deg[i][j][1] = gCat[j].size();
}
}
int[][][] winner = new int[n][n][2];
Queue<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
winner[hole][i][1] = 1; // 鼠到达洞中（此时轮到猫移动），鼠获胜
winner[i][hole][0] = 2; // 猫到达洞中（此时轮到鼠移动），猫获胜
winner[i][i][0] = winner[i][i][1] = 2; // 猫和鼠出现在同一个节点，无论轮到谁移动，都是猫获胜
q.offer(new int[]{hole, i, 1});
q.offer(new int[]{i, hole, 0});
q.offer(new int[]{i, i, 0});
q.offer(new int[]{i, i, 1});
}
while (!q.isEmpty()) {
int[] cur = q.poll();
int mouse = cur[0], cat = cur[1], turn = cur[2];
int win = winner[mouse][cat][turn]; // 最终谁赢了
for (int[] pre : getPreStates(mouse, cat, turn, gMouse, gCat, winner)) {
int preMouse = pre[0], preCat = pre[1], preTurn = turn ^ 1;
// 情况一：如果上一回合鼠从 pre 移动到 cur，最终鼠赢，那么标记 pre 状态的 winner = 鼠
// 情况二：如果上一回合猫从 pre 移动到 cur，最终猫赢，那么标记 pre 状态的 winner = 猫
// 情况三：如果上一回合鼠从 pre 移动到 cur，最终猫赢，那么待定，直到我们发现从 pre 出发能到达的状态都是猫赢，那么标记 pre 状态的 winner = 猫
// 情况四：如果上一回合猫从 pre 移动到 cur，最终鼠赢，那么待定，直到我们发现从 pre 出发能到达的状态都是鼠赢，那么标记 pre 状态的 winner = 鼠
if (preTurn == win - 1 || --deg[preMouse][preCat][preTurn] == 0) {
winner[preMouse][preCat][preTurn] = win;
q.offer(new int[]{preMouse, preCat, preTurn}); // 继续倒推
}
}
}
// 鼠在节点 mouseStart，猫在节点 catStart，当前轮到鼠移动
return winner[mouseStart][catStart][0]; // 返回最终谁赢了（或者平局）
}
// 获取 (mouse, cat, turn) 的上个状态（值尚未确定）
private List<int[]> getPreStates(int mouse, int cat, int turn, List<Integer>[] gMouse, List<Integer>[] gCat, int[][][] winner) {
List<int[]> preStates = new ArrayList<>();
if (turn == 0) { // 当前轮到鼠移动
for (int preCat : gCat[cat]) { // 上一轮猫的位置
if (winner[mouse][preCat][1] == 0) { // 猫无法移动到洞中
preStates.add(new int[]{mouse, preCat});
}
}
} else { // 当前轮到猫移动
for (int preMouse : gMouse[mouse]) { // 上一轮鼠的位置
if (winner[preMouse][cat][0] == 0) {
preStates.add(new int[]{preMouse, cat});
}
}
}
return preStates;
}
}
python3 解法, 执行用时: 231 ms, 内存消耗: 18.6 MB, 提交时间: 2025-02-11 09:27:55
class Solution:
# 913. 猫和老鼠
def catMouseGame(self, g_mouse: List[List[int]], g_cat: List[List[int]], mouse_start: int, cat_start: int, hole: int) -> int:
n = len(g_mouse)
deg = [[[0, 0] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
deg[i][j][0] = len(g_mouse[i])
deg[i][j][1] = len(g_cat[j])
winner = [[[0, 0] for _ in range(n)] for _ in range(n)]
q = deque()
for i in range(n):
winner[hole][i][1] = 1 # 鼠到达洞中（此时轮到猫移动），鼠获胜
winner[i][hole][0] = 2 # 猫到达洞中（此时轮到鼠移动），猫获胜
winner[i][i][0] = winner[i][i][1] = 2 # 猫和鼠出现在同一个节点，无论轮到谁移动，都是猫获胜
q.append((hole, i, 1))
q.append((i, hole, 0))
q.append((i, i, 0))
q.append((i, i, 1))
# 获取 (mouse, cat, turn) 的上个状态（值尚未确定）
def get_pre_states() -> List[Tuple[int, int]]:
if turn: # 当前轮到猫移动，枚举上一轮鼠的位置
return [(pre_mouse, cat) for pre_mouse in g_mouse[mouse] if winner[pre_mouse][cat][0] == 0]
# 当前轮到鼠移动，枚举上一轮猫的位置
return [(mouse, pre_cat) for pre_cat in g_cat[cat] if winner[mouse][pre_cat][1] == 0]
# 减少上个状态的度数
def dec_deg_to_zero() -> bool:
deg[pre_mouse][pre_cat][pre_turn] -= 1
return deg[pre_mouse][pre_cat][pre_turn] == 0
while q:
mouse, cat, turn = q.popleft()
win = winner[mouse][cat][turn] # 最终谁赢了
pre_turn = turn ^ 1
for pre_mouse, pre_cat in get_pre_states():
# 情况一：如果上一回合鼠从 pre 移动到 cur，最终鼠赢，那么标记 pre 状态的 winner = 鼠
# 情况二：如果上一回合猫从 pre 移动到 cur，最终猫赢，那么标记 pre 状态的 winner = 猫
# 情况三：如果上一回合鼠从 pre 移动到 cur，最终猫赢，那么待定，直到我们发现从 pre 出发能到达的状态都是猫赢，那么标记 pre 状态的 winner = 猫
# 情况四：如果上一回合猫从 pre 移动到 cur，最终鼠赢，那么待定，直到我们发现从 pre 出发能到达的状态都是鼠赢，那么标记 pre 状态的 winner = 鼠
if pre_turn == win - 1 or dec_deg_to_zero():
winner[pre_mouse][pre_cat][pre_turn] = win
q.append((pre_mouse, pre_cat, pre_turn))
# 鼠在节点 mouse_start，猫在节点 cat_start，当前轮到鼠移动
return winner[mouse_start][cat_start][0] # 返回最终谁赢了（或者平局）
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
DIRS = (0, -1), (0, 1), (-1, 0), (1, 0) # 左右上下
m, n = len(grid), len(grid[0])
# 鼠和猫分别建图
g_mouse = [[] for _ in range(m * n)]
g_cat = [[] for _ in range(m * n)]
for i, row in enumerate(grid):
for j, c in enumerate(row):
if c == '#': # 墙
continue
if c == 'M': # 鼠的位置
mx, my = i, j
elif c == 'C': # 猫的位置
cx, cy = i, j
elif c == 'F': # 食物（洞）的位置
fx, fy = i, j
v = i * n + j # 二维坐标 (i,j) 映射为一维坐标 v
for dx, dy in DIRS: # 枚举左右上下四个方向
for k in range(mouseJump + 1): # 枚举跳跃长度
x, y = i + k * dx, j + k * dy
if not (0 <= x < m and 0 <= y < n and grid[x][y] != '#'): # 出界或者遇到墙
break
g_mouse[v].append(x * n + y) # 连边
for k in range(catJump + 1): # 枚举跳跃长度
x, y = i + k * dx, j + k * dy
if not (0 <= x < m and 0 <= y < n and grid[x][y] != '#'): # 出界或者遇到墙
break
g_cat[v].append(x * n + y) # 连边
# 判断是否鼠赢
return self.catMouseGame(g_mouse, g_cat, mx * n + my, cx * n + cy, fx * n + fy) == 1
golang 解法, 执行用时: 40 ms, 内存消耗: 7.2 MB, 提交时间: 2023-06-06 10:01:19
const (
MouseTurn = 0
CatTurn = 1
UNKNOWN = 0
MouseWin = 1
CatWin = 2
MaxMoves = 1000
)
var dirs = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func canMouseWin(grid []string, catJump int, mouseJump int) bool {
rows, cols := len(grid), len(grid[0])
getPos := func(row, col int) int { return row*cols + col }
var startMouse, startCat, food int
for i, row := range grid {
for j, ch := range row {
if ch == 'M' {
startMouse = getPos(i, j)
} else if ch == 'C' {
startCat = getPos(i, j)
} else if ch == 'F' {
food = getPos(i, j)
}
}
}
// 计算每个状态的度
total := rows * cols
degrees := [64][64][2]int{}
for mouse := 0; mouse < total; mouse++ {
mouseRow := mouse / cols
mouseCol := mouse % cols
if grid[mouseRow][mouseCol] == '#' {
continue
}
for cat := 0; cat < total; cat++ {
catRow := cat / cols
catCol := cat % cols
if grid[catRow][catCol] == '#' {
continue
}
degrees[mouse][cat][MouseTurn]++
degrees[mouse][cat][CatTurn]++
for _, dir := range dirs {
for row, col, jump := mouseRow+dir.x, mouseCol+dir.y, 1; row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#' && jump <= mouseJump; jump++ {
nextMouse := getPos(row, col)
nextCat := getPos(catRow, catCol)
degrees[nextMouse][nextCat][MouseTurn]++
row += dir.x
col += dir.y
}
for row, col, jump := catRow+dir.x, catCol+dir.y, 1; row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] != '#' && jump <= catJump; jump++ {
nextMouse := getPos(mouseRow, mouseCol)
nextCat := getPos(row, col)
degrees[nextMouse][nextCat][CatTurn]++
row += dir.x
col += dir.y
}
}
}
}
results := [64][64][2][2]int{}
type state struct{ mouse, cat, turn int }
q := []state{}
// 猫和老鼠在同一个单元格，猫获胜
for pos := 0; pos < total; pos++ {
row := pos / cols
col := pos % cols
if grid[row][col] == '#' {
continue
}
results[pos][pos][MouseTurn][0] = CatWin
results[pos][pos][MouseTurn][1] = 0
results[pos][pos][CatTurn][0] = CatWin
results[pos][pos][CatTurn][1] = 0
q = append(q, state{pos, pos, MouseTurn}, state{pos, pos, CatTurn})
}
// 猫和食物在同一个单元格，猫获胜
for mouse := 0; mouse < total; mouse++ {
mouseRow := mouse / cols
mouseCol := mouse % cols
if grid[mouseRow][mouseCol] == '#' || mouse == food {
continue
}
results[mouse][food][MouseTurn][0] = CatWin
results[mouse][food][MouseTurn][1] = 0
results[mouse][food][CatTurn][0] = CatWin
results[mouse][food][CatTurn][1] = 0
q = append(q, state{mouse, food, MouseTurn}, state{mouse, food, CatTurn})
}
// 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
for cat := 0; cat < total; cat++ {
catRow := cat / cols
catCol := cat % cols
if grid[catRow][catCol] == '#' || cat == food {
continue
}
results[food][cat][MouseTurn][0] = MouseWin
results[food][cat][MouseTurn][1] = 0
results[food][cat][CatTurn][0] = MouseWin
results[food][cat][CatTurn][1] = 0
q = append(q, state{food, cat, MouseTurn}, state{food, cat, CatTurn})
}
getPrevStates := func(mouse, cat, turn int) []state {
mouseRow := mouse / cols
mouseCol := mouse % cols
catRow := cat / cols
catCol := cat % cols
prevTurn := MouseTurn
if turn == MouseTurn {
prevTurn = CatTurn
}
maxJump, startRow, startCol := catJump, catRow, catCol
if prevTurn == MouseTurn {
maxJump, startRow, startCol = mouseJump, mouseRow, mouseCol
}
prevStates := []state{{mouse, cat, prevTurn}}
for _, dir := range dirs {
for i, j, jump := startRow+dir.x, startCol+dir.y, 1; i >= 0 && i < rows && j >= 0 && j < cols && grid[i][j] != '#' && jump <= maxJump; jump++ {
prevMouseRow := mouseRow
prevMouseCol := mouseCol
prevCatRow := i
prevCatCol := j
if prevTurn == MouseTurn {
prevMouseRow = i
prevMouseCol = j
prevCatRow = catRow
prevCatCol = catCol
}
prevMouse := getPos(prevMouseRow, prevMouseCol)
prevCat := getPos(prevCatRow, prevCatCol)
prevStates = append(prevStates, state{prevMouse, prevCat, prevTurn})
i += dir.x
j += dir.y
}
}
return prevStates
}
// 拓扑排序
for len(q) > 0 {
s := q[0]
q = q[1:]
mouse, cat, turn := s.mouse, s.cat, s.turn
result := results[mouse][cat][turn][0]
moves := results[mouse][cat][turn][1]
for _, s := range getPrevStates(mouse, cat, turn) {
prevMouse, prevCat, prevTurn := s.mouse, s.cat, s.turn
if results[prevMouse][prevCat][prevTurn][0] == UNKNOWN {
canWin := result == MouseWin && prevTurn == MouseTurn || result == CatWin && prevTurn == CatTurn
if canWin {
results[prevMouse][prevCat][prevTurn][0] = result
results[prevMouse][prevCat][prevTurn][1] = moves + 1
q = append(q, state{prevMouse, prevCat, prevTurn})
} else {
degrees[prevMouse][prevCat][prevTurn]--
if degrees[prevMouse][prevCat][prevTurn] == 0 {
loseResult := MouseWin
if prevTurn == MouseTurn {
loseResult = CatWin
}
results[prevMouse][prevCat][prevTurn][0] = loseResult
results[prevMouse][prevCat][prevTurn][1] = moves + 1
q = append(q, state{prevMouse, prevCat, prevTurn})
}
}
}
}
}
return results[startMouse][startCat][MouseTurn][0] == MouseWin && results[startMouse][startCat][MouseTurn][1] <= MaxMoves
}
python3 解法, 执行用时: 912 ms, 内存消耗: 18.5 MB, 提交时间: 2023-06-06 10:00:12
# 拓扑排序
MOUSE_TURN = 0
CAT_TURN = 1
UNKNOWN = 0
MOUSE_WIN = 1
CAT_WIN = 2
MAX_MOVES = 1000
DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))
class Solution:
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
rows, cols = len(grid), len(grid[0])
def getPos(row: int, col: int) -> int:
return row * cols + col
startMouse = startCat = food = 0
for i, row in enumerate(grid):
for j, ch in enumerate(row):
if ch == 'M':
startMouse = getPos(i, j)
elif ch == 'C':
startCat = getPos(i, j)
elif ch == 'F':
food = getPos(i, j)
# 计算每个状态的度
total = rows * cols
degrees = [[[0, 0] for _ in range(total)] for _ in range(total)]
for mouse in range(total):
mouseRow, mouseCol = divmod(mouse, cols)
if grid[mouseRow][mouseCol] == '#':
continue
for cat in range(total):
catRow, catCol = divmod(cat, cols)
if grid[catRow][catCol] == '#':
continue
degrees[mouse][cat][MOUSE_TURN] += 1
degrees[mouse][cat][CAT_TURN] += 1
for dx, dy in DIRS:
row, col, jump = mouseRow + dx, mouseCol + dy, 1
while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= mouseJump:
nextMouse = getPos(row, col)
nextCat = getPos(catRow, catCol)
degrees[nextMouse][nextCat][MOUSE_TURN] += 1
row += dx
col += dy
jump += 1
row, col, jump = catRow + dx, catCol + dy, 1
while 0 <= row < rows and 0 <= col < cols and grid[row][col] != '#' and jump <= catJump:
nextMouse = getPos(mouseRow, mouseCol)
nextCat = getPos(row, col)
degrees[nextMouse][nextCat][CAT_TURN] += 1
row += dx
col += dy
jump += 1
results = [[[[0, 0], [0, 0]] for _ in range(total)] for _ in range(total)]
q = deque()
# 猫和老鼠在同一个单元格，猫获胜
for pos in range(total):
row, col = divmod(pos, cols)
if grid[row][col] == '#':
continue
results[pos][pos][MOUSE_TURN][0] = CAT_WIN
results[pos][pos][MOUSE_TURN][1] = 0
results[pos][pos][CAT_TURN][0] = CAT_WIN
results[pos][pos][CAT_TURN][1] = 0
q.append((pos, pos, MOUSE_TURN))
q.append((pos, pos, CAT_TURN))
# 猫和食物在同一个单元格，猫获胜
for mouse in range(total):
mouseRow, mouseCol = divmod(mouse, cols)
if grid[mouseRow][mouseCol] == '#' or mouse == food:
continue
results[mouse][food][MOUSE_TURN][0] = CAT_WIN
results[mouse][food][MOUSE_TURN][1] = 0
results[mouse][food][CAT_TURN][0] = CAT_WIN
results[mouse][food][CAT_TURN][1] = 0
q.append((mouse, food, MOUSE_TURN))
q.append((mouse, food, CAT_TURN))
# 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
for cat in range(total):
catRow, catCol = divmod(cat, cols)
if grid[catRow][catCol] == '#' or cat == food:
continue
results[food][cat][MOUSE_TURN][0] = MOUSE_WIN
results[food][cat][MOUSE_TURN][1] = 0
results[food][cat][CAT_TURN][0] = MOUSE_WIN
results[food][cat][CAT_TURN][1] = 0
q.append((food, cat, MOUSE_TURN))
q.append((food, cat, CAT_TURN))
def getPrevStates(mouse: int, cat: int, turn: int) -> List[Tuple[int, int, int]]:
mouseRow, mouseCol = divmod(mouse, cols)
catRow, catCol = divmod(cat, cols)
prevTurn = CAT_TURN if turn == MOUSE_TURN else MOUSE_TURN
maxJump = mouseJump if prevTurn == MOUSE_TURN else catJump
startRow = mouseRow if prevTurn == MOUSE_TURN else catRow
startCol = mouseCol if prevTurn == MOUSE_TURN else catCol
prevStates = [(mouse, cat, prevTurn)]
for dx, dy in DIRS:
i, j, jump = startRow + dx, startCol + dy, 1
while 0 <= i < rows and 0 <= j < cols and grid[i][j] != '#' and jump <= maxJump:
prevMouseRow = i if prevTurn == MOUSE_TURN else mouseRow
prevMouseCol = j if prevTurn == MOUSE_TURN else mouseCol
prevCatRow = catRow if prevTurn == MOUSE_TURN else i
prevCatCol = catCol if prevTurn == MOUSE_TURN else j
prevMouse = getPos(prevMouseRow, prevMouseCol)
prevCat = getPos(prevCatRow, prevCatCol)
prevStates.append((prevMouse, prevCat, prevTurn))
i += dx
j += dy
jump += 1
return prevStates
# 拓扑排序
while q:
mouse, cat, turn = q.popleft()
result = results[mouse][cat][turn][0]
moves = results[mouse][cat][turn][1]
for prevMouse, prevCat, prevTurn in getPrevStates(mouse, cat, turn):
if results[prevMouse][prevCat][prevTurn][0] == UNKNOWN:
if result == MOUSE_WIN and prevTurn == MOUSE_TURN or result == CAT_WIN and prevTurn == CAT_TURN:
results[prevMouse][prevCat][prevTurn][0] = result
results[prevMouse][prevCat][prevTurn][1] = moves + 1
q.append((prevMouse, prevCat, prevTurn))
else:
degrees[prevMouse][prevCat][prevTurn] -= 1
if degrees[prevMouse][prevCat][prevTurn] == 0:
loseResult = CAT_WIN if prevTurn == MOUSE_TURN else MOUSE_WIN
results[prevMouse][prevCat][prevTurn][0] = loseResult
results[prevMouse][prevCat][prevTurn][1] = moves + 1
q.append((prevMouse, prevCat, prevTurn))
return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN and results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES
python3 解法, 执行用时: 9036 ms, 内存消耗: 70.2 MB, 提交时间: 2023-06-06 09:58:16
DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)
class Solution:
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
mm, nn = len(grid), len(grid[0])
for x in range(mm):
for y in range(nn):
match grid[x][y]:
case 'C':
cat = x, y
case 'F':
food = x, y
case 'M':
mouse = x, y
@lru_cache(None)
def dfs(m, c, i):
"""
极大极小博弈，
老鼠尽量找自己获胜的，其次接受平局
猫尽量找自己获胜的，其次接受平局
:param m: 老鼠的位置
:param c: 猫的位置
:param i: 回合
"""
if m == c or c == food or i > 128:
return False
if m == food:
return True
is_cat = False
# 猫回合
if i % 2:
pos, jump = c, catJump
is_cat = True
else:
pos, jump = m, mouseJump
for dx, dy in DIRS:
for jp in range(jump + 1):
nx, ny = pos[0] + dx * jp, pos[1] + dy * jp
if nx < 0 or ny < 0 or nx >= mm or ny >= nn or grid[nx][ny] == '#':
break
if not is_cat and dfs((nx, ny), c, i + 1):
return True
elif is_cat and not dfs(m, (nx, ny), i + 1):
return False
return is_cat
return dfs(mouse, cat, 0)
