LeetCode Number of Islands

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:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

方法

实际上这道题在找实习的时候做过，现在忘了，不应该，题目实际上蛮简单的，说明还是自己方法没有理解透彻的缘故。

这道题实际上有一个小技巧，当扫描到1时，将1置为0，即若都在同一个岛上则岛都为0，再次遍历的时候只要找到一个1说明就是下一个岛。找岛时，从四边开始找

public class Solution {
    public int numIslands(char[][] grid) {
        if(grid == null){
            return 0;
        }
        int count = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0'){
            return;
        }
        grid[i][j] = '0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}