题解 | ACM中的AC题

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;
//需要注意首先找到的双人时出口不一定最优，所以bfs记录每一个步数的所有情况，此时队列中双人和单人是混合的
//为了区分单双人，还需要划分两个状态，可以用cur数组区分，当单人时，第二个人位置存储-1
//因为总是镜像移动的，所以visited可以只存储其中一个人位置
public class Main {
    static int[][] direction1 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};//右，左，下，上
    static int[][] direction2 = {{0, -1}, {0, 1}, {-1, 0},  {1, 0}}; //左，右，上，下
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            in.nextLine();
            char[][] board = new char[n][m];
            for (int i = 0; i < n; i++) {
                board[i] = in.nextLine().toCharArray();
            }
            Deque<int[]> que = new ArrayDeque<>();//混合队列int[]{x1,y1,x2,y2,步数}
            boolean[][] visited = new boolean[n][m];//双人移动记录
            boolean[][] visited2 = new boolean[n][m];//单人移动记录
            que.offer(new int[] {x, y, x, y,0});//初始位置xy，步数0
            visited[x][y]=true;
            boolean out = false;//标记是否成功出去
            int count = 0;
            while (!que.isEmpty()) {
                int[] cur = que.poll();
                //第二个人位置在-1时进入单人模式，否则进入双人模式
                //双人模式
                if(cur[2]!=-1){
                    //双人同时出去则直接break，此时步数就是最优步数
                    if(board[cur[0]][cur[1]] == '@'&&board[cur[2]][cur[3]] == '@'){
                        out=true;
                        count=cur[4];
                        break;
                    }
                    //只其中一人出去时，重新将剩下那人的位置入队列，因为目前已处在此位置所以步数不变
                    if (board[cur[0]][cur[1]] == '@') {
                        //无论出去的是谁，剩下那人的位置总是维护在cur0和1，3和4总是为-1
                        que.offer(new int[]{cur[2],cur[3],-1,-1,cur[4]});
                        visited2[cur[2]][cur[3]]=true;
                        continue;
                    }
                    if (board[cur[2]][cur[3]] == '@') {
                        que.offer(new int[]{cur[0],cur[1],-1,-1,cur[4]});
                        visited2[cur[0]][cur[1]]=true;
                        continue;
                    }
                    //遍历四个方位移动结果并入队，其中direction1和2方向相反
                    for (int i = 0; i < direction1.length; i++) {
                        int ni1 = cur[0] + direction1[i][0];
                        int nj1 = cur[1] + direction1[i][1];
                        int ni2 = cur[2] + direction2[i][0];
                        int nj2 = cur[3] + direction2[i][1];
                        if (ni1 >= 0 && nj1 >= 0 && ni1 < n && nj1 < m && ni2 >= 0 && nj2 >= 0 &&
                                ni2 < n && nj2 < m
                                && !visited[ni1][nj1]
                                && board[ni1][nj1] != '#' && board[ni2][nj2] != '#') {
                            visited[ni1][nj1]=true;
                            que.offer(new int[] {ni1, nj1, ni2, nj2,cur[4]+1});
                        }
                    }
                //单人模式
                }else{
                    if (board[cur[0]][cur[1]] == '@') {
                        out = true;
                        count=cur[4];
                        break;
                    }
                    for (int i = 0; i < direction1.length; i++) {
                        int ni1 = cur[0] + direction1[i][0];
                        int nj1 = cur[1] + direction1[i][1];
                        if (ni1 >= 0 && nj1 >= 0 && ni1 < n && nj1 < m
                                && !visited2[ni1][nj1]
                                && board[ni1][nj1] != '#') {
                            visited2[ni1][nj1]=true;
                            que.offer(new int[] {ni1, nj1, -1, -1,cur[4]+1});
                        }
                    }
                }
            }
            if (out) {
                System.out.println(count);
            } else {
                System.out.println(-1);

            }
        }
    }
}