题目描述
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。
它们所处的环境设定是一个 rows x cols
的方格 grid
,其中每个格子可能是一堵墙、一块地板、一位玩家(猫或者老鼠)或者食物。
- 玩家由字符
'C'
(代表猫)和'M'
(代表老鼠)表示。 - 地板由字符
'.'
表示,玩家可以通过这个格子。 - 墙用字符
'#'
表示,玩家不能通过这个格子。 - 食物用字符
'F'
表示,玩家可以通过这个格子。 - 字符
'C'
,'M'
和'F'
在grid
中都只会出现一次。
猫和老鼠按照如下规则移动:
- 老鼠 先移动,然后两名玩家轮流移动。
- 每一次操作时,猫和老鼠可以跳到上下左右四个方向之一的格子,它们不能跳过墙也不能跳出
grid
。 catJump
和mouseJump
是猫和老鼠分别跳一次能到达的最远距离,它们也可以跳小于最大距离的长度。- 它们可以停留在原地。
- 老鼠可以跳跃过猫的位置。
游戏有 4 种方式会结束:
- 如果猫跟老鼠处在相同的位置,那么猫获胜。
- 如果猫先到达食物,那么猫获胜。
- 如果老鼠先到达食物,那么老鼠获胜。
- 如果老鼠不能在
1000
次操作以内到达食物,那么猫获胜。
给定 rows x cols
的矩阵 grid
和两个整数 catJump
和 mouseJump
,双方都采取最优策略,如果老鼠获胜,那么请你返回 true
,否则返回 false
。
样例
输入:grid = ["####F","#C...","M...."], catJump = 1, mouseJump = 2
输出:true
解释:猫无法抓到老鼠,也没法比老鼠先到达食物。
输入:grid = ["M.C...F"], catJump = 1, mouseJump = 4
输出:true
输入:grid = ["M.C...F"], catJump = 1, mouseJump = 3
输出:false
输入:grid = ["C...#","...#F","....#","M...."], catJump = 2, mouseJump = 5
输出:false
输入:grid = [".M...","..#..","#..#.","C#.#.","...#F"], catJump = 3, mouseJump = 1
输出:true
限制
rows == grid.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j]
只包含字符'C'
,'M'
,'F'
,'.'
和'#'
。grid
中只包含一个'C'
,'M'
和'F'
。1 <= catJump, mouseJump <= 8
算法
(记忆化搜索) $O(R(mn)^2 \cdot catJump \cdot mouseJump)$
- 设计状态 $res(r, cx, cy, mx, my)$ 为第 $r$ 轮,猫在 $(cx, cy)$,老鼠在 $(mx, my)$ 时的获胜状态。
- 根据题目描述确定边界条件。
- 对于老鼠来说,如果有一条路径使得猫必败,则老鼠可以获胜。对于猫同理。
- 直接记忆化搜索求出目标状态的值。
时间复杂度
- 假设游戏最多 $R$ 轮,则最多有 $O(R(mn)^2))$ 种状态。
- 每种状态需要 $O(catJump \cdot mouseJump)$ 的时间转移。
- 故总时间复杂度为 $O(R(mn)^2 \cdot catJump \cdot mouseJump)$。
- 这里最大的 $R$ 虽然给到了 1000,但会超时。但实际中,环的大小很难超过 $mn$,取 100 可以过。
空间复杂度
- 需要 $O(R(mn)^2))$ 的额外空间存储状态。
C++ 代码
class Solution {
private:
int m, n, cj, mj;
int fx, fy;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector<string> g;
int res[100][4096];
inline int hash(int x1, int y1, int x2, int y2) {
return (x1 << 9) | (y1 << 6) | (x2 << 3) | y2;
}
int move_cat(int cx, int cy, int mx, int my, int op) {
if (op == 100)
return 1;
if (res[op][hash(cx, cy, mx, my)] != -1)
return res[op][hash(cx, cy, mx, my)];
if (cx == fx && cy == fy)
return 1;
if (mx == fx && my == fy)
return 0;
if (cx == mx && cy == my)
return 1;
for (int i = 0; i < 4; i++)
for (int j = 0; j <= cj; j++) {
int x = cx + dx[i] * j;
int y = cy + dy[i] * j;
if (x < 0 || x >= m || y < 0 || y >= n || g[x][y] == '#')
break;
if (move_mouse(x, y, mx, my, op + 1) == 0)
return res[op][hash(cx, cy, mx, my)] = 1;
}
return res[op][hash(cx, cy, mx, my)] = 0;
}
int move_mouse(int cx, int cy, int mx, int my, int op) {
if (op == 100)
return 0;
if (res[op][hash(cx, cy, mx, my)] != -1)
return res[op][hash(cx, cy, mx, my)];
if (cx == fx && cy == fy)
return 0;
if (mx == fx && my == fy)
return 1;
if (cx == mx && cy == my)
return 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j <= mj; j++) {
int x = mx + dx[i] * j;
int y = my + dy[i] * j;
if (x < 0 || x >= m || y < 0 || y >= n || g[x][y] == '#')
break;
if (move_cat(cx, cy, x, y, op + 1) == 0)
return res[op][hash(cx, cy, mx, my)] = 1;
}
return res[op][hash(cx, cy, mx, my)] = 0;
}
public:
bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {
int cx, cy, mx, my;
m = grid.size(); n = grid[0].size();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 'C') {
cx = i; cy = j;
} else if (grid[i][j] == 'M') {
mx = i; my = j;
} else if (grid[i][j] == 'F') {
fx = i; fy = j;
}
g = grid;
cj = catJump;
mj = mouseJump;
memset(res, -1, sizeof(res));
if (move_mouse(cx, cy, mx, my, 0) == 1)
return true;
return false;
}
};
这个超过1000轮 判负,这个是怎么缩水到200回合100回合即可?搞不懂,Y总说是经验值.
应该可以通过严谨的数学证明得出一个上限,根据实践经验轮数过多一般都是进入了环
ok
谢谢