网易编程题---地牢逃脱（广度优先遍历）

来源

牛客网2017校招编程题

题目描述：

给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。

根据题目的描述可知，要求出在最坏情况下需要多少步逃离地牢，只需求出入口到所有可通行位置的最小距离，并取其最大值即可。广度优先算法最适合解决这种无向无权图的最短路径问题，所有该问题可转化成利用bfs算法找到入口到所有可通行位置的最短距离。这道题目需要注意的是返回-1的情况，也就是说存在从出口位置不能到达所有可通行位置的情况，所以我们应该记录一个图中所有可通行位置的总数量，在bfs算法结束时，判断该数量是否减为0，换句话来说就是判断所有可通行位置是否被我们的bfs算法处理了。如果数量最后为0，那么最大的步数就是答案，如果不为0，那么答案必为-1。

AC代码如下：

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

public class Main2 {
    private static int[][] d; //方向和步长
    private static boolean[][] visited; //该位置是否被访问过
    static class Position{
        int x;
        int y;
        Position(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    private static int bfs(char[][] chars, Position root, int left){
        LinkedList<Position> queue = new LinkedList<>();
        queue.add(root);
        int dis = 0;    //最长的步数
        int cur = 1;   //当前需要处理的位置数量
        int next = 0;  //处理完当前位置之后，还需处理的位置数量
        visited[root.x][root.y] = true;  
        while(!queue.isEmpty()){
            Position curPos = queue.removeFirst();
            left--;  //剩余的可通行位置
            cur--;  
            if(left == 0)     //如果剩余位置为0，那么就已经找到了最大距离，直接返回就好了
                  return dis;
            for(int i = 0 ; i < d.length ; i++){
                int newX = curPos.x + d[i][0];
                int newY = curPos.y + d[i][1];
                if(newX >= 0 && newX < chars.length && newY >= 0 && newY < chars[0].length
                        && !visited[newX][newY] && chars[newX][newY] != 'X')
                {
                    visited[newX][newY] = true;    //把下次要访问的位置设为真，避免再将此次位置放入队列
                    queue.add(new Position(newX, newY));  //将下次位置添加进队尾
                    next++;
                }
            }
            if(cur == 0){      //如果当前已经没有要处理的位置，那么说明已经找到所有由这个位置出发的位置了，这个位置就没有利用价值了，此时需要将距离加+1到达下一步的位置
                dis++;
                cur = next;
                next = 0;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int left = 0;
        char[][] chars = new char[n][m];
        scanner.nextLine();    //读入nextInt()的换行符，不能省略！
        for(int i = 0 ; i < n ; i++)
            chars[i] = scanner.nextLine().toCharArray();
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
                if(chars[i][j] == '.')
                    left++;
        int beginX = scanner.nextInt();
        int beginY = scanner.nextInt();
        int dNum = scanner.nextInt();
        d = new int[dNum][2];
        visited = new boolean[n][m];
        for(int i = 0 ; i < dNum ; i++)
            for(int j = 0 ; j < 2 ; j++)
                d[i][j] = scanner.nextInt();
        System.out.println(bfs(chars, new Position(beginX, beginY), left));
    }
}