当前位置：网站首页>力扣解法汇总1728-猫和老鼠 II
力扣解法汇总1728-猫和老鼠 II
2022-06-12 02:04:00 【失落夏天】
目录链接：
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目：
https://github.com/September26/java-algorithms
原题链接：力扣
描述：
一只猫和一只老鼠在玩一个叫做猫和老鼠的游戏。
它们所处的环境设定是一个 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.length
cols = grid[i].length
1 <= rows, cols <= 8
grid[i][j] 只包含字符 'C' ，'M' ，'F' ，'.' 和 '#' 。
grid 中只包含一个 'C' ，'M' 和 'F' 。
1 <= catJump, mouseJump <= 8
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/cat-and-mouse-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
没做出来，看官方题解的。
动态规划的方案超时了
代码：
public class Solution1728 {
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;
}
}边栏推荐
- 没有文笔，大家多多包涵
- How to automatically color cells in Excel
- 力扣解法汇总449-序列化和反序列化二叉搜索树
- How to improve the advertising rating of advertising, that is, the quality score?
- LeetCode Algorithm 997. Find the town judge
- 为什么我们要使用谷歌搜索广告？
- Pagination writing of PHP security open 10 article list module
- 力扣解法汇总942-增减字符串匹配
- Comprehensive quality of teaching resources in the second half of 2019 - subjective questions
- "China Dongxin Cup" the fourth programming competition of Guangxi University (synchronous competition)
猜你喜欢
The release of star ring kundb 2.2 provides a new choice for business systems with high concurrent transactions and queries
入手Ticwatch2
如何最大化的利用各种匹配方式？ ——Google SEM
Graphic data analysis | business cognition and data exploration
Does the virtual host have independent IP
How to stop anti-virus software from blocking a web page? Take gdata as an example
Subject knowledge and educational ability of information technology in the first half of 2019 – subjective questions
MySQL表常用操作思维导图
混泥土（地面+墙面）+ 山体裂缝数据集汇总（分类及目标检测）
MySQL advanced knowledge points
随机推荐
Summary of concrete (ground + wall) + Mountain crack data set (classification and target detection)
力扣解法汇总面试题 17.11-单词距离
The establishment and introduction of the announcement module of PHP development blog system
Educational knowledge and ability test questions of primary and secondary school educational endowment examination in the second half of 2019 (middle school) - subjective questions
Metaverse × How will smart cities develop?
入手Ticwatch2
Three main factors determining advertising quality
leetcodeSQL:612. Nearest distance on plane
力扣解法汇总436-寻找右区间
Graphical data analysis | data analysis tool map
How WPS inserts a directory and the operating steps for quickly inserting a directory
How to improve the advertising rating of advertising, that is, the quality score?
lua 函数
Freshman year: learning summary
[adjustment] notice on the opening of the 2022 pre adjustment system for postgraduate enrollment of Shanghai Second University of Technology
android html5页面加载缓存优化
PHP security development 13 column module of blog system
力扣解法汇总699-掉落的方块
通用树形结构的迭代与组合模式实现方案
PHP builds a high-performance API architecture based on sw-x framework (III)