[leetcode/lintcode 题解] 阿里算法面试真题：扫雷

描述
现在有一个简易版的扫雷游戏。你将得到一个n*m大小的二维数组作为游戏地图。
每个位置上有一个值（0或1，1代表此处没有雷，0表示有雷）。
你将获得一个起点的位置坐标（x，y），x表示所在行数，y表示所在列数（x，y均从0开始计数）。
若当下位置上没有雷，则上下左右四个方向均可以到达，若当下位置有雷，则不能再往新的方向移动。
返回所有可以到达的坐标。
0<n,m<=200.
答案返回一个任意顺序的数组，数组包括所有可以到达的位置坐标。

在线评测地址：领扣题库官网

样例1
输入: 
[[1,0,0,0],[1,0,0,0],[0,1,1,1],[0,1,0,0]]
[0,1]
输出: 
[[0,1]]
解释：
[0,1]位置上是0，不能再往新的地方走，只能到达这一个位置

样例2
输入: 
[[1,0,0,0],[1,0,0,0],[0,1,1,1],[0,1,0,0]]
[1,0]
输出: 
[[0,0],[1,0],[1,1],[2,0],[0,1]]
解释：
[1,0]位置上是1，所以可以走到[[0,0],[1,1],[2,0]],其中只有[0,0]位置上是1可以继续走到[0,1],然后不能再走了。

解法：
BFS (宽度优先搜索)
算法 / 数据结构：BFS / 队列

解题思路
首先将起点压入队列中，不断获取队首元素并弹出队列，判断当前点上下边界是否越界、是否为地雷、是否到达过，然后将下一个可到达的点压入队列中，直到队列为空。

复杂度分析：
时间复杂度：O(n*m)
n为矩阵的行，m为矩阵的列，最坏的情况就是所有点都要遍历一次。
空间复杂度：O(n*m)
n为矩阵的行，m为矩阵的列，最坏的情况就是所有点都要遍历一次,并记录在visited中。

源代码

public class Solution {
    /**
     * @param Mine_map: an array represents the map.
     * @param Start: the start position.
     * @return: return an array including all reachable positions.
     */
    public List<List<Integer>> Mine_sweeping(int[][] Mine_map, int[] Start) {
        
        Queue<List<Integer>> queue = new LinkedList<>();
        List<List<Integer>> answer = new ArrayList<>();
        Map<List<Integer>, Boolean> visited = new HashMap<>();
        int row = Mine_map.length;
        int col = Mine_map[0].length;
        
        queue.offer(Arrays.asList(Start[0], Start[1]));
        
        while (!queue.isEmpty()) {
            List<Integer> current = queue.poll();
            int curX = current.get(0);
            int curY = current.get(1);
            answer.add(Arrays.asList(curX, curY));
            if (Mine_map[curX][curY] == 0) {
                continue;
            }
            visited.put(Arrays.asList(curX, curY), true);
            if (curX - 1 >= 0 && !visited.containsKey(Arrays.asList(curX - 1, curY))) {
                visited.put(Arrays.asList(curX - 1, curY), true);
                queue.offer(Arrays.asList(curX - 1, curY));
            }
            if (curX + 1 < row && !visited.containsKey(Arrays.asList(curX + 1, curY))) {
                visited.put(Arrays.asList(curX + 1, curY), true);
                queue.offer(Arrays.asList(curX + 1, curY));
            }
            if (curY - 1 >= 0 && !visited.containsKey(Arrays.asList(curX, curY - 1))) {
                visited.put(Arrays.asList(curX, curY - 1), true);
                queue.offer(Arrays.asList(curX, curY - 1));
            }
            if (curY + 1 <col && !visited.containsKey(Arrays.asList(curX, curY + 1))) {
                visited.put(Arrays.asList(curX, curY + 1), true);
                queue.offer(Arrays.asList(curX, curY + 1));
            }
        }
        
        return answer;
    }
}

更多题解参考：九章官网solution