Leetcode 200. Number of Islands 典型联通问题探讨

题目大意

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

联通问题

这道题的本质是在一个图中寻找联通成分 connection component, 本题在此类问题中具有很强的代表性。寻找联通成分大致可以分为以下几个步骤：
1. 依次遍历所有节点，找到联通成分的起始结点
2. 从起始结点开始，遍历这个联通成分
3. 遍历过程中，同步更新visited集合

如同之前的各道题目一样，遍历可以有两种模式，即采用BFS遍历和DFS遍历，本题两种遍历方法复杂性一致，DFS代码更加简洁，BFS思路更加易懂。

BFS提交 (1.64%)

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

        HashSet<List<Integer>> visited = new HashSet<>();
        if (grid==null|grid.length==0||grid[0].length==0) return 0;
        int xlen = grid.length;
        int ylen = grid[0].length;
        int result = 0;
        for (int x=0;x<xlen;x++){
            for (int y=0;y<ylen;y++){
                if ( grid[x][y]=='0' || visited.contains(Arrays.asList(x,y))) continue;
                List<List<Integer>> queue = new ArrayList<>();
                List<Integer> root = Arrays.asList(x,y);
                queue.add(root);visited.add(root);
                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;
    }
}

之所以BFS解法这么慢，最重要的原因是我们单独维护了一个visited的hashset, 用于保存已经被访问计算过的结点；而每次探索过程中，都需要访问visited hashset以确定是否继续。这是一种可以接受的方法，但是不够聪明。

DFS 提交（100%）

这里采用了一个非常聪明的方法维护访问状态，也就是将访问过的结点置为0，此后不再被认为为land结点，从而不再影响后面的计算。

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