题目:
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的情况，就停止探索。一边探索一边存储当前见到的1的数量。如果对grid(i,j)做dfs，获得至少1个1，则算做1个island。累加islands的数量即可得到答案。

时间复杂度 O(n)，因为每个数组元素只被访问了一次

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