题目描述

blablabla

代码

package bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


class pointxy{
    int x;
    int y;
    public pointxy(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

}
public class 迷宫问题 {

    public static int N=1010,n;
    public static int g[][]=new int [N][N];
    public static pointxy path[][]=new pointxy[N][N];
    public static int step[][]=new int [N][N];

    public static  int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
  //  public static int dy[]={0,0,1,-1};

    public static void  bfs(int x,int y) {

        Queue<pointxy> queue =new LinkedList<pointxy>();
        queue.add(new pointxy(x, y));
        step[x][y]=0;
        //System.out.println(step[x][y]);
        while(!queue.isEmpty()){
            pointxy t=queue.poll();
            //System.out.println(t.x+" "+t.y);
            //System.out.println("tttt");
            for(int i=0;i<4;i++){
                int a=t.x+dx[i];
                int b=t.y+dy[i];
                if(a>=n || b>=n || a<0 || b<0) continue;
                if(g[a][b]==1) continue;
                if(step[a][b]!=-1)continue;

                step[a][b]=1+step[t.x][t.y];
                path[a][b]=t;

                queue.add(new pointxy(a,b));

            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
     BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));

     n=Integer.parseInt(bufferedReader.readLine());
     // System.out.println(n);
     for(int i=0;i<N;i++) Arrays.fill(step[i], -1);

     for(int i=0;i<n;i++){
         String p[]=bufferedReader.readLine().split(" ");
         for(int j=0;j<n;j++){
        g[i][j]=Integer.parseInt(p[j]);
         }
     }


     bfs(n-1,n-1);
    // System.out.println(step[0][0]);

    int x=0;
    int y=0;
    while(true){
        System.out.println(x+" "+y);
        if(x==n-1 && y==n-1) break;
        pointxy pointxy = path[x][y];
        x=pointxy.x;
        y=pointxy.y;
    }


    }

}