题目描述

走迷宫

JAVA 代码

带Queue队列的解法

import java.io.*;
import java.util.*;

class Main{
    static int N = 110;
    //g为地图, d为距离
    static int[][] g = new int [N][N], d = new int[N][N];
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        //读入地图
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                g[i][j] = sc.nextInt();
            }
        }
        System.out.println(bfs(n,m));
        sc.close();
    }

    public static int bfs(int n, int m){
        Queue<int[]> q = new LinkedList<>();
        d[0][0] = 0;//初始距离为0
        int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};//用向量判断往哪走.
        q.offer(new int[] {0,0});// 加入左上角的值.

        while(!q.isEmpty()){
            int a[] = q.poll();

            //四个方向走一下. 
            for(int i =0;i<4;i++){
                //a[0]为x的值, a[1]为y的值
                int x = a[0]+dx[i], y = a[1]+dy[i];
                //如果在边界内, 并且没走过.
                if(x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==0){
                    d[x][y] = d[a[0]][a[1]] + 1;
                    q.offer(new int[] {x,y});
                }
            }
        }
        return d[n-1][m-1];
    }


}