题解 | #走迷宫#

广度优先 走过标记/不再走

//最短路径
import java.util.*;
//最短路径
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String[] s1=sc.nextLine().split(" ");
        int n=Integer.parseInt(s1[0]);
        int m=Integer.parseInt(s1[1]);
        String[] s2=sc.nextLine().split(" ");
        int sti=Integer.parseInt(s2[0]);
        int stj=Integer.parseInt(s2[1]);
        int ovi=Integer.parseInt(s2[2]);
        int ovj=Integer.parseInt(s2[3]);
        char[][] arr=new char[n][m];
        for(int i=0;i<n;i++){
            String s=sc.nextLine();

            for(int j=0;j<m;j++){
                arr[i][j]=s.charAt(j);
            }
        }
        if(arr[sti-1][stj-1]=='*' || arr[ovi-1][ovj-1]=='*') {
            System.out.println(-1);
            return;
        }
        Queue<int[]> queue=new LinkedList<>();
//        queue.offer(new Node(0,sti-1,stj-1));
        int[] node={0,sti-1,stj-1};
        queue.offer(node);
        int result=minStep(n,m,arr,ovi-1,ovj-1,queue);
        System.out.println(result);
    }
    public static int minStep(int n,int m,char[][] arr,int  ovi,int ovj,Queue<int[]> queue){
        while(queue.size()!=0) {
            int[] node = queue.poll();
            int step = node[0];
            int i = node[1];
            int j = node[2];
            if (i == ovi && j == ovj) return step;
            if (j + 1 < m && arr[i][j + 1] == '.') {
                int[] node1 = {step + 1, i, j + 1};
                queue.offer(node1);
                arr[i][j + 1] = '/';
            }
            if (i + 1 < n && arr[i + 1][j] == '.') {
                int[] node1 = {step + 1, i + 1, j};
                queue.offer(node1);
                arr[i + 1][j] = '/';
            }
            if (j - 1 >= 0 && arr[i][j - 1] == '.') {
                int[] node1 = {step + 1, i, j - 1};
                queue.offer(node1);
                arr[i][j - 1] = '/';
            }
            if (i - 1 >= 0 && arr[i - 1][j] == '.') {
                int[] node1 = {step + 1, i - 1, j};
                queue.offer(node1);
                arr[i - 1][j] = '/';
            }
        }
        return -1;
    }
}