AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

力扣——1728. 猫和老鼠 II（Java、C代码）

2022-11-23 133
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 力扣——1728. 猫和老鼠 II（Java、C代码）

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

class Solution {
    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;
    }
}

在这里插入图片描述

C代码：

static const int MOUSE_TURN = 0, CAT_TURN = 1;
static const int UNKNOWN = 0, MOUSE_WIN = 1, CAT_WIN = 2;
static const int MAX_MOVES = 1000;

#define MAX_QUEUE_SIZE 10000

int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int g_rows, g_cols;
char **g_grid;
int g_catJump, g_mouseJump;
int g_food;
int g_degrees[64][64][2];
int g_results[64][64][2][2];

int getPos(int row, int col) {
    return row * g_cols + col;
}

typedef struct State {
    int mouse;
    int cat;
    int turn;
} State;

typedef struct Node {
    State currState;
    struct Node * next;
} Node;

Node * getPrevStates(int mouse, int cat, int turn) {
    Node * prevStates = NULL;
    Node * tail = NULL;
    int mouseRow = mouse / g_cols, mouseCol = mouse % g_cols;
    int catRow = cat / g_cols, catCol = cat % g_cols;
    int prevTurn = turn == MOUSE_TURN ? CAT_TURN : MOUSE_TURN;
    int maxJump = prevTurn == MOUSE_TURN ? g_mouseJump : g_catJump;
    int startRow = prevTurn == MOUSE_TURN ? mouseRow : catRow;
    int startCol = prevTurn == MOUSE_TURN ? mouseCol : catCol;
    prevStates = (Node *)malloc(sizeof(Node));
    tail = prevStates;
    tail->currState.mouse = mouse;
    tail->currState.cat = cat;
    tail->currState.turn = prevTurn;
    tail->next = NULL;
    for (int k = 0; k < 4; k++) {
        int *dir = dirs[k];
        for (int i = startRow + dir[0], j = startCol + dir[1], jump = 1; i >= 0 && i < g_rows && j >= 0 && j < g_cols && g_grid[i][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);
            tail->next = (Node *)malloc(sizeof(Node));
            tail = tail->next;
            tail->currState.mouse = prevMouse;
            tail->currState.cat = prevCat;
            tail->currState.turn = prevTurn;
            tail->next = NULL;
        }
    }
    return prevStates;
}

bool canMouseWin(char ** grid, int gridSize, int catJump, int mouseJump){
    g_rows = gridSize;
    g_cols = strlen(grid[0]);
    g_grid = grid;
    g_catJump = catJump;
    g_mouseJump = mouseJump;
    int startMouse = -1, startCat = -1;
    for (int i = 0; i < g_rows; i++) {
        for (int j = 0; j < g_cols; j++) {
            char c = grid[i][j];
            if (c == 'M') {
                startMouse = getPos(i, j);
            } else if (c == 'C') {
                startCat = getPos(i, j);
            } else if (c == 'F') {
                g_food = getPos(i, j);
            }
        }
    }
    int total = g_rows * g_cols;
    memset(g_degrees, 0, sizeof(g_degrees));
    memset(g_results, 0, sizeof(g_results));
    State * queue = (State *)malloc(sizeof(State) * MAX_QUEUE_SIZE);
    int head = 0, tail = 0;
    // 计算每个状态的度
    for (int mouse = 0; mouse < total; mouse++) {
        int mouseRow = mouse / g_cols, mouseCol = mouse % g_cols;
        if (grid[mouseRow][mouseCol] == '#') {
            continue;
        }
        for (int cat = 0; cat < total; cat++) {
            int catRow = cat / g_cols, catCol = cat % g_cols;
            if (grid[catRow][catCol] == '#') {
                continue;
            }
            g_degrees[mouse][cat][MOUSE_TURN]++;
            g_degrees[mouse][cat][CAT_TURN]++;
            for (int i = 0; i < 4; i++) {
                int * dir = dirs[i];
                for (int row = mouseRow + dir[0], col = mouseCol + dir[1], jump = 1; row >= 0 && row < g_rows && col >= 0 && col < g_cols && grid[row][col] != '#' && jump <= mouseJump; row += dir[0], col += dir[1], jump++) {
                    int nextMouse = getPos(row, col), nextCat = getPos(catRow, catCol);
                    g_degrees[nextMouse][nextCat][MOUSE_TURN]++;
                }
                for (int row = catRow + dir[0], col = catCol + dir[1], jump = 1; row >= 0 && row < g_rows && col >= 0 && col < g_cols && grid[row][col] != '#' && jump <= catJump; row += dir[0], col += dir[1], jump++) {
                    int nextMouse = getPos(mouseRow, mouseCol), nextCat = getPos(row, col);
                    g_degrees[nextMouse][nextCat][CAT_TURN]++;
                }
            }
        }
    }
    // 猫和老鼠在同一个单元格，猫获胜
    for (int pos = 0; pos < total; pos++) {
        int row = pos / g_cols, col = pos % g_cols;
        if (grid[row][col] == '#') {
            continue;
        }
        g_results[pos][pos][MOUSE_TURN][0] = CAT_WIN;
        g_results[pos][pos][MOUSE_TURN][1] = 0;
        g_results[pos][pos][CAT_TURN][0] = CAT_WIN;
        g_results[pos][pos][CAT_TURN][1] = 0;
        queue[tail].mouse = pos;
        queue[tail].cat = pos;
        queue[tail].turn = MOUSE_TURN;
        tail++;
        queue[tail].mouse = pos;
        queue[tail].cat = pos;
        queue[tail].turn = CAT_TURN;
        tail++;
    }
    // 猫和食物在同一个单元格，猫获胜
    for (int mouse = 0; mouse < total; mouse++) {
        int mouseRow = mouse / g_cols, mouseCol = mouse % g_cols;
        if (grid[mouseRow][mouseCol] == '#' || mouse == g_food) {
            continue;
        }
        g_results[mouse][g_food][MOUSE_TURN][0] = CAT_WIN;
        g_results[mouse][g_food][MOUSE_TURN][1] = 0;
        g_results[mouse][g_food][CAT_TURN][0] = CAT_WIN;
        g_results[mouse][g_food][CAT_TURN][1] = 0;
        queue[tail].mouse = mouse;
        queue[tail].cat = g_food;
        queue[tail].turn = MOUSE_TURN;
        tail++;
        queue[tail].mouse = mouse;
        queue[tail].cat = g_food;
        queue[tail].turn = CAT_TURN;
        tail++;
    }
    // 老鼠和食物在同一个单元格且猫和食物不在同一个单元格，老鼠获胜
    for (int cat = 0; cat < total; cat++) {
        int catRow = cat / g_cols, catCol = cat % g_cols;
        if (grid[catRow][catCol] == '#' || cat == g_food) {
            continue;
        }
        g_results[g_food][cat][MOUSE_TURN][0] = MOUSE_WIN;
        g_results[g_food][cat][MOUSE_TURN][1] = 0;
        g_results[g_food][cat][CAT_TURN][0] = MOUSE_WIN;
        g_results[g_food][cat][CAT_TURN][1] = 0;
        queue[tail].mouse = g_food;
        queue[tail].cat = cat;
        queue[tail].turn = MOUSE_TURN;
        tail++;
        queue[tail].mouse = g_food;
        queue[tail].cat = cat;
        queue[tail].turn = CAT_TURN;
        tail++;
    }
    // 拓扑排序
    while (head != tail) {
        int mouse = queue[head].mouse;
        int cat = queue[head].cat;
        int turn = queue[head].turn;
        head++;
        int result = g_results[mouse][cat][turn][0];
        int moves = g_results[mouse][cat][turn][1];
        Node * prevStates = getPrevStates(mouse, cat, turn);
        for (Node * curr = prevStates; curr; curr = curr->next) {
            int prevMouse = curr->currState.mouse;
            int prevCat = curr->currState.cat;
            int prevTurn = curr->currState.turn;
            if (g_results[prevMouse][prevCat][prevTurn][0] == UNKNOWN) {
                bool canWin = (result == MOUSE_WIN && prevTurn == MOUSE_TURN) || (result == CAT_WIN && prevTurn == CAT_TURN);
                if (canWin) {
                    g_results[prevMouse][prevCat][prevTurn][0] = result;
                    g_results[prevMouse][prevCat][prevTurn][1] = moves + 1;
                    queue[tail].mouse = prevMouse;
                    queue[tail].cat = prevCat;
                    queue[tail].turn = prevTurn;
                    tail++;
                } else {
                    g_degrees[prevMouse][prevCat][prevTurn]--;
                    if (g_degrees[prevMouse][prevCat][prevTurn] == 0) {
                        int loseResult = prevTurn == MOUSE_TURN ? CAT_WIN : MOUSE_WIN;
                        g_results[prevMouse][prevCat][prevTurn][0] = loseResult;
                        g_results[prevMouse][prevCat][prevTurn][1] = moves + 1;
                        queue[tail].mouse = prevMouse;
                        queue[tail].cat = prevCat;
                        queue[tail].turn = prevTurn;
                        tail++;
                    }
                }
            }
        }
    }
    free(queue);
    return g_results[startMouse][startCat][MOUSE_TURN][0] == MOUSE_WIN && g_results[startMouse][startCat][MOUSE_TURN][1] <= MAX_MOVES;
}

在这里插入图片描述

作者：KJ.JK

本文仅用于交流学习，未经作者允许，禁止转载，更勿做其他用途，违者必究。
文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习

文章标签：
Java
关键词：
Java代码
LeetCode java
LeetCode代码
力扣Java
LeetCode老鼠
KJ.JK
目录
相关文章
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java 索引
java实现桶排序（详细解释代码和逻辑）
java实现桶排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
20 3
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java 索引
java实现插入排序（详细解释代码和逻辑）
java实现插入排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
17 2
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
Java Shell
java实现希尔排序（详细解释代码和逻辑）
java实现希尔排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
21 1
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java 索引
java实现选择排序（详细解释代码和逻辑）
java实现选择排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
19 1
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java 索引
java实现快速排序（详细解释代码和逻辑）
java实现快速排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
47 3
萝卜带泥
|
2天前
|
Java 开发者
Java中的Lambda表达式：简化你的代码之旅
【8月更文挑战第17天】 在编程的海洋中，简洁是航行的风帆。Lambda表达式，作为Java 8的一大亮点，为开发者提供了一种更为紧凑、易读的编码方式。本篇文章将带你领略Lambda表达式的魅力，从基础概念到实际应用，让你的代码像诗句一样流畅。
萝卜带泥
12 4
众所周知
|
1天前
|
Java 开发者
在Java编程的广阔天地中，if-else与switch语句犹如两位老练的舵手，引领着代码的流向，决定着程序的走向。
在Java编程中，if-else与switch语句是条件判断的两大利器。本文通过丰富的示例，深入浅出地解析两者的特点与应用场景。if-else适用于逻辑复杂的判断，而switch则在处理固定选项或多分支选择时更为高效。从逻辑复杂度、可读性到性能考量，我们将帮助你掌握何时选用哪种语句，让你在编程时更加得心应手。无论面对何种挑战，都能找到最适合的解决方案。
众所周知
5 1
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java
java实现计数排序（详细解释代码和逻辑）
java实现计数排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
18 5
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java
java实现归并排序（详细解释代码和逻辑）
java实现归并排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
14 4
如夜了我衣衫太薄便归家靠路灯
|
6天前
|
搜索推荐 Java
java实现堆排序（详细解释代码和逻辑）
java实现堆排序（详细解释代码和逻辑）
如夜了我衣衫太薄便归家靠路灯
17 3

热门文章

最新文章

  • 1
    Java 基础【03】序列化和反序列化
  • 2
    Windows2003 配置 tomcat+jdk（java）+JDBC+SQL2000
  • 3
    java转义符和正则表达式转义符
  • 4
    Eclipse 中java跨工程调用类
  • 5
    Java语言实现简单FTP软件------&gt;本地文件管理模块的实现(九)
  • 6
    java: 警告: 源发行版 11 需要目标发行版 11”错误解决(解决方案整合)
  • 7
    Java基本数据类型与位运算
  • 8
    C#与Java对比学习：类型判断、类与接口继承、代码规范与编码习惯、常量定义
  • 9
    黑马程序员java笔记之十-----银行管理系统
  • 10
    用Java实现按字节长度截取字符串的方法
  • 1
    [leetcode] 快乐数 E
    32
  • 2
    [leetcode 链表] 反转链表 vs 链表相交
    32
  • 3
    [leetcode] 705. 设计哈希集合
    34
  • 4
    [leetcode~dfs]1261. 在受污染的二叉树中查找元素
    33
  • 5
    [leetcode] 670. 最大交换 M
    31
  • 6
    [leetcode～数位动态规划] 2719. 统计整数数目 hard
    38
  • 7
    刷题之Leetcode160题(超级详细)
    31
  • 8
    刷题之Leetcode206题(超级详细)
    36
  • 9
    刷题之Leetcode707题(超级详细)
    34
  • 10
    刷题之Leetcode35题(超级详细)
    28

    • 相关课程

    更多
  • Java面试疑难点解析 - Java Web开发
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 基于ECS搭建Java Web开发环境
  • 使用Aliyun Java Intializr进行项目开发
  • 搭建Java Web开发环境
  • 部署基于Dragonwell的Java运行环境
  • 阿里云平台上进行Java程序的编译与运行
    • 下一篇
    通义千问API入门教程