Leetcode 286. Walls and Gates 联通类型问题

题目表述

You are given a m x n 2D grid initialized with these three possible values.

-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example:

Given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

联通类型问题

分析这道题目时，可以联系Leetcode 200. Number of Islands这道题一起分析，这一类问题可以通称为联通类型问题，或者用更加形象的语言，我们都在一个矩阵中寻找一个“水中孤岛”。而两者的思路是非常类似的，都是寻找到一个孤岛点，然后向外扩张探索，遍历这个岛屿所有覆盖的点，而后循环往复指导所有孤岛点都已经被覆盖。

这个类型的问题有两种通用解法，即BFS解法和DFS解法。而经过比较，我认为DFS写法的代码更加简洁，效率也更高。因为BFS解法，即层次遍历，需要维护额外的 visited和 queue两个数据结构，而更新这些数据结构的时间也比较长。而DFS依托于递归来控制变量，不需要额外的数据结构，并且复杂性上与BFS等价。

BFS 代码 (1.53%)

class Solution {
    public int numIslands(char[][] grid) {

        HashSet<List<Integer>> visited = new HashSet<>();
        List<List<Integer>> landList = new ArrayList<>();
        if (grid==null|grid.length==0||grid[0].length==0) return 0;
        int xlen = grid.length;
        int ylen = grid[0].length;
        for (int i=0;i<xlen;i++){
            for (int j=0;j<ylen;j++){
                if (grid[i][j]=='1') landList.add(Arrays.asList(i,j));
            }
        }
        int result = 0;
        for (List<Integer> land:landList){
            if (visited.contains(land)) continue;
            List<List<Integer>> queue = new ArrayList<>();
            queue.add(land);visited.add(land);
            while (!queue.isEmpty()){
                //System.out.printf("============\n");
                int num = queue.size();
                for (int k=0;k<num;k++){
                    List<Integer> point = queue.remove(0);
                    int i = point.get(0);
                    int j = point.get(1);
                    //System.out.printf("point:[%d,%d]\n",i,j);
                    if (i>0 && grid[i-1][j]=='1' && !visited.contains(Arrays.asList(i-1,j))) {
                        visited.add(Arrays.asList(i-1,j));
                        queue.add(Arrays.asList(i-1,j));
                    }
                    if (i<xlen-1 && grid[i+1][j]=='1' && !visited.contains(Arrays.asList(i+1,j))){
                        visited.add(Arrays.asList(i+1,j));
                        queue.add(Arrays.asList(i+1,j));
                    }
                    if (j>0 && grid[i][j-1]=='1' && !visited.contains(Arrays.asList(i,j-1))){
                        visited.add(Arrays.asList(i,j-1));
                        queue.add(Arrays.asList(i,j-1));
                    }
                    if (j<ylen-1 && grid[i][j+1]=='1' && !visited.contains(Arrays.asList(i,j+1))){
                        visited.add(Arrays.asList(i,j+1));
                        queue.add(Arrays.asList(i,j+1));
                    }
                }
            }
            result++;
        }
        return result;
    }
}

DFS 代码 (100.00%)

我们在用DFS算法的时候要注意一个trick, 我把它称之为 前置判断 vs 后置判断。
在递归过程中，我们将一组参数从当前递归传递到下一层递归的过程中，需要进行条件判断，以排除非法情况，比如数组越界等等。所谓前置判断，就是在传递参数之前判断（参照上述BFS算法）；而后置判断，就是在子递归函数中进行判断（即下面的DFS算法）。

在这个类型的问题中，我认为前置判断是一个更好的选择；有利于更加简洁有力地体现出代码逻辑，简化编码过程；而效率上两者没有质的区别。比如本题中每个分支会产生4个子分支，因此有4组部分重叠的判断条件；而采用前置判断之后，只使用了一个判断句。

class Solution {

    private int xlen;
    private int ylen;
    private char[][] grid;

    public int numIslands(char[][] grid) {
        xlen = grid.length;
        if (xlen == 0) return 0;
        ylen = grid[0].length;
        this.grid = grid;

        int result = 0;
        for (int x = 0; x < xlen; x++)
            for (int y = 0; y < ylen; y++)
                if (grid[x][y] == '1') {
                    result++;
                    dfs(x, y);
                }

        return result;
    }

    private void dfs(int x, int y) {
        if (x < 0 || y < 0 || x >= xlen || y >= ylen || grid[x][y] == '0')
            return;
        grid[x][y] = '0';
        dfs(x + 1, y);
        dfs(x - 1, y);
        dfs(x, y + 1);
        dfs(x, y - 1);
    }
}