题解 | #小喵觅食#

看了其他人AC的代码，一脸懵逼，这都是啥玩意儿。参考哔哩哔哩题目讲解的思路，自己写了一下。

import java.util.*;

public class Main {
    
    static final int VISITED = -1;
    static final int UNVISITED = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int r1 = sc.nextInt();
        int r2 = sc.nextInt();
        // 漂亮美眉和猫咪的坐标
        int px = 0, py = 0, mx = 0, my = 0;
        sc.nextLine();
        int[][] maze = new int[n][m];
        for (int i = 0; i < n; i++) {
            char[] chars = sc.nextLine().toCharArray();
            for (int j = 0; j < m; j++) {
                switch (chars[j]) {
                    case 'P':
                        px = i;
                        py = j;
                        break;
                    case 'M':
                        mx = i;
                        my = j;
                        break;
                    case '*':
                        maze[i][j] = -1;
                        break;
                    default:
                        break;
                }
            }
        }
        if (bfs(maze, px, py, mx, my, r1, r2)) {
            int steps = bfs(maze, mx, my);
            System.out.println(steps == Integer.MAX_VALUE ? -1 : steps);
        } else {
            System.out.println(-1);
        }
    }

    static class Point {
        int x, y, step;

        public Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

    static public boolean bfs(int[][] maze, int px, int py, int mx, int my, int r1, int r2) {
        // 可以移动的方向 上下左右
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int m = maze.length;
        int n = maze[0].length;
        // 在不在猫的嗅觉范围内
        boolean cat = false;
        Queue<Point> queue = new LinkedList<>();
        // 入口入队
        queue.offer(new Point(px, py, 0));
        // 标记为已访问过
        maze[px][py] = VISITED;
        while (!queue.isEmpty()) {
            Point poll = queue.poll();
            // 枚举四个方向
            for (int k = 0; k < dx.length; k++) {
                int x = poll.x + dx[k];
                int y = poll.y + dy[k];
                // 没越界
                boolean isNotOutOfBound = x >= 0 && x < m && y >= 0 && y < n;
                // 没有访问过 且 在漂亮妹妹的活动范围内
                if (isNotOutOfBound && maze[x][y] == UNVISITED && isInTheRange(x, y, px, py, r1)) {
                    // 标记为已访问过
                    maze[x][y] = VISITED;
                    // 在猫的嗅觉范围内
                    if (isInTheRange(x, y, mx, my, r2)) {
                        cat = true;
                        // 更新这个地图 maze[i][j]的值为-1表示"已经访问过"或者"障碍物" 总之不再访问
                        // 大于0 表示漂亮妹妹走到这里需要几步
                        maze[x][y] = poll.step + 1;
                        continue;
                    }
                    queue.offer(new Point(x, y, poll.step + 1));
                }
            }
        }
        return cat;
    }

    static public int bfs(int[][] maze, int mx, int my) {
        // 可以移动的方向 上下左右
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        int m = maze.length;
        int n = maze[0].length;
        Queue<Point> queue = new LinkedList<>();
        // 入口入队
        queue.offer(new Point(mx, my, 0));
        // 标记为已访问过
        maze[mx][my] = VISITED;
        int min = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            Point poll = queue.poll();
            // 枚举四个方向
            for (int k = 0; k < dx.length; k++) {
                int x = poll.x + dx[k];
                int y = poll.y + dy[k];
                // 没越界
                boolean isNotOutOfBound = x >= 0 && x < m && y >= 0 && y < n;
                // 猫咪只要嗅到了小鱼干，就可以到处跑，没有距离限制
                if (isNotOutOfBound && maze[x][y] != VISITED) {
                    // 如果这是漂亮美眉可达的地方
                    if (maze[x][y] > 0) {
                        min = Math.min(min, maze[x][y] + poll.step + 1);
                    } else {
                        // 标记为已访问过
                        maze[x][y] = VISITED;
                    }
                    queue.offer(new Point(x, y, poll.step + 1));
                }
            }
        }
        return min;
    }

    static boolean isInTheRange(int x1, int y1, int x2, int y2, int r) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2) <= r;
    }
}