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

05/06/2017 更新

今天ustopia出了这道题。两个月后再动手做的时候，想到了一个visited[][]的数组，递归中什么时候count++也想到比较清楚了，但是不知道怎么才能从一个island跨越到另一个。一直想要在dfs中用for，思维局限了，其实在外面用双重for循环就行了。

    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        int count = 0;
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (floodFill(i, j, visited, grid)) {
                    count++;
                }
            }
        return count;
    }

    private boolean floodFill(int x, int y, boolean[][] visited, char[][] grid) {
        if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1' && !visited[x][y]) {
            visited[x][y] = true;
            floodFill(x - 1, y, visited, grid);
            floodFill(x + 1, y, visited, grid);
            floodFill(x, y - 1, visited, grid);
            floodFill(x, y + 1, visited, grid);
            return true;
        } else {
            return false;
        }
    }

Initial Ver

这题跟word search那题流程几乎一样，都是两个for循环内的每一个节点向四个方向dfs。
昨天覃超直播提到这种四处扩散的DFS其实是一种floodfill算法。
这种题跟NQUEENS那种NP问题又不一样，那种是dfs里含有for，更难以理解。

//为了让dfs少些参数，把一些dfs不改变的参数定义成全局变量。
    private int mRow;
    private int mCol;
    private char[][] mGrid;

    public int numIslands(char[][] grid) {
        mRow = grid.length;
        if (mRow == 0) return 0;
        mCol = grid[0].length;
        mGrid = grid;
        int count = 0;
        for (int i = 0; i < mRow; i++)
            for (int j = 0; j < mCol; j++) {
                if (dfs(i, j)) {
                    count++;
                }
            }
        return count;
    }
    private boolean dfs(int i, int j) {
        if (i >= 0 && i < mRow && j >= 0 && j < mCol && mGrid[i][j] == '1') {
            //这个就类似于visited数组，但这个不用恢复现场。我知道不恢复是可以的，但是我加了恢复的语句就不能AC了，不知道为什么。
            mGrid[i][j] = '4';
            dfs(i + 1, j);
            dfs(i - 1, j);
            dfs(i, j + 1);
            dfs(i, j - 1);
            return true;
        } else return false;
    }

solutions里的另一个解法：

public class Solution {

private int n;
private int m;

public int numIslands(char[][] grid) {
    int count = 0;
    n = grid.length;
    if (n == 0) return 0;
    m = grid[0].length;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++)
            if (grid[i][j] == '1') {
                DFSMarking(grid, i, j);
                ++count;
            }
    }    
    return count;
}

private void DFSMarking(char[][] grid, int i, int j) {
    if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') return;
    grid[i][j] = '0';
    DFSMarking(grid, i + 1, j);
    DFSMarking(grid, i - 1, j);
    DFSMarking(grid, i, j + 1);
    DFSMarking(grid, i, j - 1);
  }
}