[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

本文转自网络，原文链接：https://developer.aliyun.com/article/784030
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！