题解

题目难度：hard

知识点：迷宫搜索类问题，利用BFS找到最短路径。

分析：

将人所在位置与箱子所在位置以及所走步数看作整体，新建节点Node。首先初始位置入队，通过移动不断将还没有经过的下一位置节点入队，直至找到箱子之前箱子的位置是不变的；当人找到箱子之后（即在箱子的一侧，上下左右），开始推箱子往另一侧走（下上右左），此时人和箱子的位置都开始移动，直至走到终点或无路可走结束。
本题可以分为2个过程：（具体实现思想见代码中注释）
① 人在找到箱子之前单独移动，箱子原地不动；在这个过程中，人要从“S”走到箱子“0”的旁边（上下左右）。
② 人找到箱子之后和箱子一起向“另一侧”移动，..S0.. -> ...S0. 。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {

    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        char[][] chas=new char[n][m];
        // 人的起始位置S 以及箱子的位置
        int startX=0,startY=0,boxX=0,boxY=0;
        // 判断位置 ，即人要先找到箱子，再推着箱子往前走
        for(int i=0;i<n;i++){   
            String string=sc.next();
            for(int j=0;j<m;j++){
                chas[i][j]=string.charAt(j);
                if(chas[i][j]=='S'){
                    startX=i;
                    startY=j;
                }
                if(chas[i][j]=='0'){
                    boxX=i;
                    boxY=j;
                }
            }
        }
        System.out.println(solve(chas,startX,startY,boxX,boxY));
    }

    public static class Node{
        int px;  // 人的位置
        int py;
        int bx;  //箱子的位置
        int by;
        int step;  //从初始位置到现在节点所走的步数
        public Node(int px,int py,int bx,int by){
            this.px=px;
            this.py=py;
            this.bx=bx;
            this.by=by;
        }
    }


    private static int solve(char[][] chas,int startX, int startY,int boxX,int boxY) {
        Node start=new Node(startX, startY,boxX,boxY);
        int n=chas.length;
        int m=chas[0].length;
        // iswalked四维数组，可以用来存储走过的路径以防重复。
        int[][][][] iswalked=new int[n][m][n][m];
        // 每个节点都有dir4个方向的移动，分别是  下右上左   
        int[][] movedir=new int[][]{{1,0},{0,1},{-1,0},{0,-1}};  

        Queue<Node> que=new LinkedList<>();  //利用队列实现BFS
        start.step=0;
        que.add(start);

        //开始BFS广度搜索最短路径
        while(!que.isEmpty()){
            Node cur=que.poll();
            int newBx=cur.bx;
            int newBy=cur.by;
            for(int i=0;i<4;i++){  // 向4个方向走

                //人在箱子左边或右边
                if(cur.px==cur.bx){

                     if (cur.py+movedir[i][1]==cur.by){
                         newBy = cur.by+movedir[i][1];
                     }else{
                         newBy = cur.by;
                     }

                }  

              //人在箱子上面或下面 
                if(cur.py==cur.by){
                    if(cur.px+movedir[i][0]==cur.bx){
                        newBx = cur.bx+movedir[i][0];
                    }else{
                        newBx = cur.bx;
                    }
               }


                // 箱子找到了要随人往4个方向动；没找到则箱子不动人动
                Node next=new Node(cur.px+movedir[i][0], cur.py+movedir[i][1],newBx,newBy); 
                //不能让人在没找到箱子之前出地图或者自己提前到目的地
                if(next.px<0||next.px>=n||next.py<0||next.py>=m||chas[next.px][next.py]=='#'   
                        ||next.bx<0||next.bx>=n||next.by<0||next.by>=m
                        ||chas[next.bx][next.by]=='#'){
                    continue;
                }

                // 0说明这条路径没有走过
                if(iswalked[next.px][next.py][next.bx][next.by]==0){  
                    iswalked[next.px][next.py][next.bx][next.by]=1;
                    next.step=cur.step+1;
                    if(chas[next.bx][next.by]=='E'){   //此时把箱子推到终点了
                        return next.step;  // 最先到终点的就是最短路径
                    }
                    que.add(next);
                }
            }
        }
        return -1;
    }


}