題目:
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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

分析:
對每一個格子做dfs探索橫豎的四個方向，如果碰到visited過的元素账月，超過邊界洒敏，格子值為0的情況杰标，就停止探索评雌。一邊探索一邊存儲當(dāng)前見到的1的數(shù)量酗钞。如果對grid(i,j)做dfs败玉，獲得至少1個1劈愚，則算做1個island茄蚯。累加islands的數(shù)量即可得到答案压彭。

時間復(fù)雜度 O(n)，因?yàn)槊總€數(shù)組元素只被訪問了一次

class Solution {
    private int dfs(char[][] grid, boolean[][] visited, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;
        // Out of bound, or visited
        if(i < 0 || i >= rows || j < 0 || j >= cols || visited[i][j] == true || grid[i][j] == '0')
            return 0;
        visited[i][j] = true;

        int total = 1;
        total = total + dfs(grid, visited, i, j - 1);
        total = total + dfs(grid, visited, i, j + 1);
        total = total + dfs(grid, visited, i - 1, j);
        total = total + dfs(grid, visited, i + 1, j);

        return total;


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

        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];

        int total = 0;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                int ret = 0;
                if(visited[i][j] == false) {
                    ret = dfs(grid, visited, i, j);
                    if (ret != 0)
                        total++;
                }
            }
        }
        return total;
    }
}

簡化一下可以寫成這樣:

class Solution {
    private void dfs(char[][] grid, int i, int j) {
        // Out of bound, or visited
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
            return;        
        grid[i][j] = '0';
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
    }
    public int numIslands(char[][] grid) {
        if(grid.length == 0) return 0;
        int total = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1') {
                    dfs(grid, i, j);
                    total++;                    
                }
            }
        }
        return total;
    }
}