-
Notifications
You must be signed in to change notification settings - Fork 4
/
CatAndMouseII.java
163 lines (158 loc) · 7.67 KB
/
CatAndMouseII.java
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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
package com.dbc;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class CatAndMouseII {
static final int MOUSE_TURN = 0, CAT_TURN = 1;
static final int UNKNOWN = 0, MOUSE_WIN = 1, CAT_WIN = 2;
static final int MAX_MOVES = 1000;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int rows, cols;
String[] grid;
int catJump, mouseJump;
int food;
int[][][] degrees;
int[][][][] results;
public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
this.rows = grid.length;
this.cols = grid[0].length();
this.grid = grid;
this.catJump = catJump;
this.mouseJump = mouseJump;
int startMouse = -1, startCat = -1;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
char c = grid[i].charAt(j);
if (c == 'M') {
startMouse = getPos(i, j);
} else if (c == 'C') {
startCat = getPos(i, j);
} else if (c == 'F') {
food = getPos(i, j);
}
}
}
int total = rows * cols;
degrees = new int[total][total][2];
results = new int[total][total][2][2];
Queue<int[]> queue = new ArrayDeque<int[]>();
// 计算每个状态的度
for (int mouse = 0; mouse < total; mouse++) {
int mouseRow = mouse / cols, mouseCol = mouse % cols;
if (grid[mouseRow].charAt(mouseCol) == '#') {
continue;
}
for (int cat = 0; cat < total; cat++) {
int catRow = cat / cols, catCol = cat % cols;
if (grid[catRow].charAt(catCol) == '#') {
continue;
}
degrees[mouse][cat][MOUSE_TURN]++;
degrees[mouse][cat][CAT_TURN]++;
for (int[] dir : dirs) {
for (int row = mouseRow + dir[0], col = mouseCol + dir[1], jump = 1; row >= 0 && row < rows && col >= 0 && col < cols && grid[row].charAt(col) != '#' && jump <= mouseJump; row += dir[0], col += dir[1], jump++) {
int nextMouse = getPos(row, col), nextCat = getPos(catRow, catCol);
degrees[nextMouse][nextCat][MOUSE_TURN]++;
}
for (int row = catRow + dir[0], col = catCol + dir[1], jump = 1; row >= 0 && row < rows && col >= 0 && col < cols && grid[row].charAt(col) != '#' && jump <= catJump; row += dir[0], col += dir[1], jump++) {
int nextMouse = getPos(mouseRow, mouseCol), nextCat = getPos(row, col);
degrees[nextMouse][nextCat][CAT_TURN]++;
}
}
}
}
// 猫和老鼠在同一个单元格，猫获胜
for (int pos = 0; pos < total; pos++) {
int row = pos / cols, col = pos % cols;
if (grid[row].charAt(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;
queue.offer(new int[]{pos, pos, MOUSE_TURN});
queue.offer(new int[]{pos, pos, CAT_TURN});
}
// 猫和食物在同一个单元格，猫获胜
for (int mouse = 0; mouse < total; mouse++) {
int mouseRow = mouse / cols, mouseCol = mouse % cols;
if (grid[mouseRow].charAt(mouseCol) == '#' || 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;
queue.offer(new int[]{mouse, food, MOUSE_TURN});
queue.offer(new int[]{mouse, food, CAT_TURN});
}
// 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
for (int cat = 0; cat < total; cat++) {
int catRow = cat / cols, catCol = cat % cols;
if (grid[catRow].charAt(catCol) == '#' || 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;
queue.offer(new int[]{food, cat, MOUSE_TURN});
queue.offer(new int[]{food, cat, CAT_TURN});
}
// 拓扑排序
while (!queue.isEmpty()) {
int[] state = queue.poll();
int mouse = state[0], cat = state[1], turn = state[2];
int result = results[mouse][cat][turn][0];
int moves = results[mouse][cat][turn][1];
List<int[]> prevStates = getPrevStates(mouse, cat, turn);
for (int[] prevState : prevStates) {
int prevMouse = prevState[0], prevCat = prevState[1], prevTurn = prevState[2];
if (results[prevMouse][prevCat][prevTurn][0] == UNKNOWN) {
boolean canWin = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
if (canWin) {
results[prevMouse][prevCat][prevTurn][0] = result;
results[prevMouse][prevCat][prevTurn][1] = moves + 1;
queue.offer(new int[]{prevMouse, prevCat, prevTurn});
} else {
degrees[prevMouse][prevCat][prevTurn]--;
if (degrees[prevMouse][prevCat][prevTurn] == 0) {
int loseResult = prevTurn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
results[prevMouse][prevCat][prevTurn][0] = loseResult;
results[prevMouse][prevCat][prevTurn][1] = moves + 1;
queue.offer(new int[]{prevMouse, prevCat, prevTurn});
}
}
}
}
}
return results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN && results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES;
}
public List<int[]> getPrevStates(int mouse, int cat, int turn) {
List<int[]> prevStates = new ArrayList<int[]>();
int mouseRow = mouse / cols, mouseCol = mouse % cols;
int catRow = cat / cols, catCol = cat % cols;
int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
int maxJump = prevTurn == MOUSE_TURN ? mouseJump : catJump;
int startRow = prevTurn == MOUSE_TURN ? mouseRow : catRow;
int startCol = prevTurn == MOUSE_TURN ? mouseCol : catCol;
prevStates.add(new int[]{mouse, cat, prevTurn});
for (int[] dir : dirs) {
for (int i = startRow + dir[0], j = startCol + dir[1], jump = 1; i >= 0 && i < rows && j >= 0 && j < cols && grid[i].charAt(j) != '#' && jump <= maxJump; i += dir[0], j += dir[1], jump++) {
int prevMouseRow = prevTurn == MOUSE_TURN ? i : mouseRow;
int prevMouseCol = prevTurn == MOUSE_TURN ? j : mouseCol;
int prevCatRow = prevTurn == MOUSE_TURN ? catRow : i;
int prevCatCol = prevTurn == MOUSE_TURN ? catCol : j;
int prevMouse = getPos(prevMouseRow, prevMouseCol);
int prevCat = getPos(prevCatRow, prevCatCol);
prevStates.add(new int[]{prevMouse, prevCat, prevTurn});
}
}
return prevStates;
}
public int getPos(int row, int col) {
return row * cols + col;
}
}