题目描述

1为障碍物，只能走0
问：从左上角走到右下角最短需要几步

输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出

9

bfs+队列(完美组合) : 求最短的路径（不是带权值图的最短路径）

http://poj.org/problem?id=3984(这题求出经过的坐标)

java

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

public class 迷宫问题bfs {

    static int map[][];
    static int n,m;
    static int[] dirx = { 1, -1, 0, 0 };
    static int[] diry = { 0, 0, 1, -1 };
    static int[][] vis=new int[5][5];
    static class Node {
        int x;
        int y;
        int depth;

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

    public static void bfs(int a, int b, int cnt) {
        //先进后出
        Queue<Node> q = new LinkedList<>();
        Node n1 = new Node(a, b, cnt);
        map[0][0]=1;        //变成障碍，就不能走了，也可以另开一个二维数组记录走过的坐标
        q.add(n1);
        while (!q.isEmpty()) {

            Node poll = q.poll();
            int depth = poll.depth;     

            if (poll.x == 4 && poll.y == 4) {
                System.out.println(depth);
                break;
            }

            //四个方向
            for(int i=0;i<4;i++) {
                int x = poll.x + dirx[i];
                int y = poll.y + diry[i];
                if (x >= 0 && x < 5 && y >= 0 && y < 5 && map[x][y]==0) {
                    map[x][y]=1;        //变成障碍，就不能走了，也可以另开一个二维数组记录走过的坐标
                    q.add(new Node(x, y, depth + 1));
                }
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            for(int j=0;j<m;j++) {
                map[i][j]=sc.nextInt();
            }
        }
        bfs(0, 0, 1);       //起点也包括
    }
}