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

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 (宽度优先搜索)

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) {

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);
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));
}
}

}
}

+ 订阅