数据结构-怀化学院期末题（59）

题目描述：

迷宫求最短路径。
只能走上、下，左、右四个方向。
输入：
输入只有一个用例。
第一行为迷宫大小,n,m，即n行m列，
第二行为起点位置，
第三行为终点位置，
接下来的为迷宫图，1表示墙壁，0表示通道

输出：
输出从起点到终点的最短路径，即最少走的步数

输入样例：

10 10
2 2
9 9
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

输出样例：

14 

代码：

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;

public class no59 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int sx = in.nextInt();
        int sy = in.nextInt();
        int ex = in.nextInt();
        int ey = in.nextInt();
        int[][] map = new int[110][110];
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                map[i][j] = in.nextInt();

        System.out.printf("%d",bfs(n,m,sx,sy,map,ex,ey));
    }
    public static int bfs(int n,int m,int sx,int sy,int[][] map,int ex,int ey){
        int[][] book = new int[110][110];
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        int[][] lu = new int[110][110];
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(sx,sy));
        book[sx][sy]=1;
        while(!q.isEmpty()){
             Node t = q.peek();
             q.poll();
             if(t.x == ex && t.y == ey){
                return lu[ex][ey];
             }
             for(int i = 0;i < 4;i ++){
                 int qx = t.x + dx[i];
                 int qy = t.y + dy[i];
                 if(qx>0&&qy>0&&qx<=n&&qy<=m&&book[qx][qy]==0&&map[qx][qy]==0){
                     book[qx][qy] = 1;
                     lu[qx][qy] = lu[t.x][t.y] + 1;
                     q.offer(new Node(qx,qy));
                 }
             }
        }
        return lu[ex][ey];
    }
    static class Node{
        int x;int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}