题目描述
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。
它们所处的环境设定是一个 rows x cols 的方格 grid ，其中每个格子可能是一堵墙、一块地板、一位玩家（猫或者老鼠）或者食物。
- 玩家由字符
'C' （代表猫）和 'M' （代表老鼠）表示。
- 地板由字符
'.' 表示，玩家可以通过这个格子。
- 墙用字符
'#' 表示，玩家不能通过这个格子。
- 食物用字符
'F' 表示，玩家可以通过这个格子。
- 字符
'C' ， 'M' 和 'F' 在 grid 中都只会出现一次。
猫和老鼠按照如下规则移动：
- 老鼠 先移动 ，然后两名玩家轮流移动。
- 每一次操作时，猫和老鼠可以跳到上下左右四个方向之一的格子，他们不能跳过墙也不能跳出
grid 。
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
示例 4：
输入：grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
输出：false
示例 5：
输入：grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
输出：true
提示：
rows == grid.lengthcols = grid[i].length1 <= rows, cols <= 8grid[i][j] 只包含字符 'C' ，'M' ，'F' ，'.' 和 '#' 。grid 中只包含一个 'C' ，'M' 和 'F' 。1 <= catJump, mouseJump <= 8
解法
方法一：拓扑排序
根据题目描述，游戏中的状态由老鼠的位置、猫的位置和移动方决定。当状态为以下情况，可以直接确定胜负：
- 当猫和老鼠的位置相同时，猫获胜，这是猫的必胜状态，老鼠的必败状态。
- 当猫先到达食物时，猫获胜，这是猫的必胜状态，老鼠的必败状态。
- 当老鼠先到达食物时，老鼠获胜，这是老鼠的必胜状态，猫的必败状态。
为了得到初始状态的游戏结果，需要从边界状态开始遍历所有的状态。每个状态包含老鼠的位置、猫的位置和移动方，根据当前状态可以得到上一轮的所有可能状态，上一轮状态的移动方和当前状态的移动方相反，上一轮状态的移动方在上一轮状态的位置和当前状态的位置不同。
我们用元组 \((m, c, t)\) 表示本轮的状态，用 \((pm, pc, pt)\) 表示上一轮可能的状态，那么上一轮的所有可能状态有：
- 如果本轮的移动方是老鼠，那么上一轮的移动方是猫，上一轮的老鼠位置是本轮老鼠位置，上一轮的猫位置是本轮猫位置的所有邻接点。
- 如果本轮的移动方是猫，那么上一轮的移动方是老鼠，上一轮的猫位置是本轮猫位置，上一轮的老鼠位置是本轮老鼠位置的所有邻接点。
初始时，除了边界状态以外，其他所有状态的结果都是未知的。我们从边界状态开始，对于每个状态，得到上一轮的所有可能状态并更新结果，更新的逻辑如下：
- 如果上一轮的移动方与本轮的获胜方相同，那么上一轮的移动方可以到达当前状态并获胜，直接更新上一轮的状态为本轮的获胜方。
- 如果上一轮的移动方与本轮的获胜方不同，且上一轮的移动方可以到达的所有状态都是上一轮的移动方的必败状态，那么我们将上一轮的状态更新为本轮的获胜方。
对于第 \(2\) 个更新逻辑，我们需要记录每个状态的度。初始时，每个状态的度表示该状态的移动方可以移动到的结点数，即移动方所在节点的相邻结点数，如果移动方是猫且所在结点与洞相邻则需要将该状态的度减 \(1\)。
当所有状态的结果都更新完毕时，初始状态的结果即为最终结果。
时间复杂度 \(O(m^2 \times n^2 \times (m + n)\)，空间复杂度 \(O(m^2 \times n^2)\)。其中 \(m\) 和 \(n\) 分别是矩阵的行数和列数。
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
73
74
75
76
77
78
79
80
81
82
83
84
85 | class Solution:
def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
m, n = len(grid), len(grid[0])
cat_start = mouse_start = food = 0
dirs = (-1, 0, 1, 0, -1)
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
v = i * n + j
if c == "C":
cat_start = v
elif c == "M":
mouse_start = v
elif c == "F":
food = v
for a, b in pairwise(dirs):
for k in range(mouseJump + 1):
x, y = i + k * a, j + k * b
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 * a, j + k * b
if not (0 <= x < m and 0 <= y < n and grid[x][y] != "#"):
break
g_cat[v].append(x * n + y)
return self.calc(g_mouse, g_cat, mouse_start, cat_start, food) == 1
def calc(
self,
g_mouse: List[List[int]],
g_cat: List[List[int]],
mouse_start: int,
cat_start: int,
hole: int,
) -> int:
def get_prev_states(state):
m, c, t = state
pt = t ^ 1
pre = []
if pt == 1:
for pc in g_cat[c]:
if ans[m][pc][1] == 0:
pre.append((m, pc, pt))
else:
for pm in g_mouse[m]:
if ans[pm][c][0] == 0:
pre.append((pm, c, 0))
return pre
n = len(g_mouse)
degree = [[[0, 0] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
degree[i][j][0] = len(g_mouse[i])
degree[i][j][1] = len(g_cat[j])
ans = [[[0, 0] for _ in range(n)] for _ in range(n)]
q = deque()
for i in range(n):
ans[hole][i][1] = 1
ans[i][hole][0] = 2
ans[i][i][1] = ans[i][i][0] = 2
q.append((hole, i, 1))
q.append((i, hole, 0))
q.append((i, i, 0))
q.append((i, i, 1))
while q:
state = q.popleft()
t = ans[state[0]][state[1]][state[2]]
for prev_state in get_prev_states(state):
pm, pc, pt = prev_state
if pt == t - 1:
ans[pm][pc][pt] = t
q.append(prev_state)
else:
degree[pm][pc][pt] -= 1
if degree[pm][pc][pt] == 0:
ans[pm][pc][pt] = t
q.append(prev_state)
return ans[mouse_start][cat_start][0]
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119 | class Solution {
private final int[] dirs = {-1, 0, 1, 0, -1};
public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
int m = grid.length;
int n = grid[0].length();
int catStart = 0, mouseStart = 0, food = 0;
List<Integer>[] gMouse = new List[m * n];
List<Integer>[] gCat = new List[m * n];
Arrays.setAll(gMouse, i -> new ArrayList<>());
Arrays.setAll(gCat, i -> new ArrayList<>());
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char c = grid[i].charAt(j);
if (c == '#') {
continue;
}
int v = i * n + j;
if (c == 'C') {
catStart = v;
} else if (c == 'M') {
mouseStart = v;
} else if (c == 'F') {
food = v;
}
for (int d = 0; d < 4; ++d) {
for (int k = 0; k <= mouseJump; k++) {
int x = i + k * dirs[d];
int y = j + k * dirs[d + 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 * dirs[d];
int y = j + k * dirs[d + 1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x].charAt(y) == '#') {
break;
}
gCat[v].add(x * n + y);
}
}
}
}
return calc(gMouse, gCat, mouseStart, catStart, food) == 1;
}
private int calc(
List<Integer>[] gMouse, List<Integer>[] gCat, int mouseStart, int catStart, int hole) {
int n = gMouse.length;
int[][][] degree = new int[n][n][2];
int[][][] ans = new int[n][n][2];
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
degree[i][j][0] = gMouse[i].size();
degree[i][j][1] = gCat[j].size();
}
}
for (int i = 0; i < n; i++) {
ans[hole][i][1] = 1;
ans[i][hole][0] = 2;
ans[i][i][1] = 2;
ans[i][i][0] = 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[] state = q.poll();
int m = state[0], c = state[1], t = state[2];
int result = ans[m][c][t];
for (int[] prevState : getPrevStates(gMouse, gCat, state, ans)) {
int pm = prevState[0], pc = prevState[1], pt = prevState[2];
if (pt == result - 1) {
ans[pm][pc][pt] = result;
q.offer(prevState);
} else {
degree[pm][pc][pt]--;
if (degree[pm][pc][pt] == 0) {
ans[pm][pc][pt] = result;
q.offer(prevState);
}
}
}
}
return ans[mouseStart][catStart][0];
}
private List<int[]> getPrevStates(
List<Integer>[] gMouse, List<Integer>[] gCat, int[] state, int[][][] ans) {
int m = state[0], c = state[1], t = state[2];
int pt = t ^ 1;
List<int[]> pre = new ArrayList<>();
if (pt == 1) {
for (int pc : gCat[c]) {
if (ans[m][pc][1] == 0) {
pre.add(new int[] {m, pc, pt});
}
}
} else {
for (int pm : gMouse[m]) {
if (ans[pm][c][0] == 0) {
pre.add(new int[] {pm, c, 0});
}
}
}
return pre;
}
}
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 | class Solution {
private:
const int dirs[5] = {-1, 0, 1, 0, -1};
int calc(vector<vector<int>>& gMouse, vector<vector<int>>& gCat, int mouseStart, int catStart, int hole) {
int n = gMouse.size();
vector<vector<vector<int>>> degree(n, vector<vector<int>>(n, vector<int>(2)));
vector<vector<vector<int>>> ans(n, vector<vector<int>>(n, vector<int>(2)));
queue<tuple<int, int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
degree[i][j][0] = gMouse[i].size();
degree[i][j][1] = gCat[j].size();
}
}
for (int i = 0; i < n; i++) {
ans[hole][i][1] = 1;
ans[i][hole][0] = 2;
ans[i][i][1] = 2;
ans[i][i][0] = 2;
q.push(make_tuple(hole, i, 1));
q.push(make_tuple(i, hole, 0));
q.push(make_tuple(i, i, 0));
q.push(make_tuple(i, i, 1));
}
while (!q.empty()) {
auto state = q.front();
q.pop();
int m = get<0>(state), c = get<1>(state), t = get<2>(state);
int result = ans[m][c][t];
for (auto& prevState : getPrevStates(gMouse, gCat, state, ans)) {
int pm = get<0>(prevState), pc = get<1>(prevState), pt = get<2>(prevState);
if (pt == result - 1) {
ans[pm][pc][pt] = result;
q.push(prevState);
} else {
degree[pm][pc][pt]--;
if (degree[pm][pc][pt] == 0) {
ans[pm][pc][pt] = result;
q.push(prevState);
}
}
}
}
return ans[mouseStart][catStart][0];
}
vector<tuple<int, int, int>> getPrevStates(vector<vector<int>>& gMouse, vector<vector<int>>& gCat, tuple<int, int, int>& state, vector<vector<vector<int>>>& ans) {
int m = get<0>(state), c = get<1>(state), t = get<2>(state);
int pt = t ^ 1;
vector<tuple<int, int, int>> pre;
if (pt == 1) {
for (int pc : gCat[c]) {
if (ans[m][pc][1] == 0) {
pre.push_back(make_tuple(m, pc, pt));
}
}
} else {
for (int pm : gMouse[m]) {
if (ans[pm][c][0] == 0) {
pre.push_back(make_tuple(pm, c, 0));
}
}
}
return pre;
}
public:
bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
int m = grid.size();
int n = grid[0].length();
int catStart = 0, mouseStart = 0, food = 0;
vector<vector<int>> gMouse(m * n);
vector<vector<int>> gCat(m * n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char c = grid[i][j];
if (c == '#') {
continue;
}
int v = i * n + j;
if (c == 'C') {
catStart = v;
} else if (c == 'M') {
mouseStart = v;
} else if (c == 'F') {
food = v;
}
for (int d = 0; d < 4; ++d) {
for (int k = 0; k <= mouseJump; k++) {
int x = i + k * dirs[d];
int y = j + k * dirs[d + 1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
break;
}
gMouse[v].push_back(x * n + y);
}
for (int k = 0; k <= catJump; k++) {
int x = i + k * dirs[d];
int y = j + k * dirs[d + 1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '#') {
break;
}
gCat[v].push_back(x * n + y);
}
}
}
}
return calc(gMouse, gCat, mouseStart, catStart, food) == 1;
}
};
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111 | func canMouseWin(grid []string, catJump int, mouseJump int) bool {
m, n := len(grid), len(grid[0])
catStart, mouseStart, food := 0, 0, 0
dirs := []int{-1, 0, 1, 0, -1}
gMouse := make([][]int, m*n)
gCat := make([][]int, m*n)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
c := grid[i][j]
if c == '#' {
continue
}
v := i*n + j
if c == 'C' {
catStart = v
} else if c == 'M' {
mouseStart = v
} else if c == 'F' {
food = v
}
for d := 0; d < 4; d++ {
a, b := dirs[d], dirs[d+1]
for k := 0; k <= mouseJump; k++ {
x, y := i+k*a, j+k*b
if !(0 <= x && x < m && 0 <= y && y < n && grid[x][y] != '#') {
break
}
gMouse[v] = append(gMouse[v], x*n+y)
}
for k := 0; k <= catJump; k++ {
x, y := i+k*a, j+k*b
if !(0 <= x && x < m && 0 <= y && y < n && grid[x][y] != '#') {
break
}
gCat[v] = append(gCat[v], x*n+y)
}
}
}
}
return calc(gMouse, gCat, mouseStart, catStart, food) == 1
}
func calc(gMouse, gCat [][]int, mouseStart, catStart, hole int) int {
n := len(gMouse)
degree := make([][][]int, n)
ans := make([][][]int, n)
for i := 0; i < n; i++ {
degree[i] = make([][]int, n)
ans[i] = make([][]int, n)
for j := 0; j < n; j++ {
degree[i][j] = make([]int, 2)
ans[i][j] = make([]int, 2)
degree[i][j][0] = len(gMouse[i])
degree[i][j][1] = len(gCat[j])
}
}
q := list.New()
for i := 0; i < n; i++ {
ans[hole][i][1] = 1
ans[i][hole][0] = 2
ans[i][i][1] = 2
ans[i][i][0] = 2
q.PushBack([]int{hole, i, 1})
q.PushBack([]int{i, hole, 0})
q.PushBack([]int{i, i, 0})
q.PushBack([]int{i, i, 1})
}
for q.Len() > 0 {
front := q.Front()
q.Remove(front)
state := front.Value.([]int)
m, c, t := state[0], state[1], state[2]
currentAns := ans[m][c][t]
for _, prevState := range getPrevStates(gMouse, gCat, m, c, t, ans) {
pm, pc, pt := prevState[0], prevState[1], prevState[2]
if pt == currentAns-1 {
ans[pm][pc][pt] = currentAns
q.PushBack([]int{pm, pc, pt})
} else {
degree[pm][pc][pt]--
if degree[pm][pc][pt] == 0 {
ans[pm][pc][pt] = currentAns
q.PushBack([]int{pm, pc, pt})
}
}
}
}
return ans[mouseStart][catStart][0]
}
func getPrevStates(gMouse, gCat [][]int, m, c, t int, ans [][][]int) [][]int {
pt := t ^ 1
pre := [][]int{}
if pt == 1 {
for _, pc := range gCat[c] {
if ans[m][pc][1] == 0 {
pre = append(pre, []int{m, pc, pt})
}
}
} else {
for _, pm := range gMouse[m] {
if ans[pm][c][0] == 0 {
pre = append(pre, []int{pm, c, pt})
}
}
}
return pre
}
|