[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