摘要：同時我們每找到一個，就將其標為，這樣就能把整個島嶼變成。我們只要記錄對矩陣遍歷時能進入多少次搜索，就代表有多少個島嶼。

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

時間 O(NM) 空間 O(max(N,M)) 遞歸棧空間

我們遍歷矩陣的每一個點，對每個點都嘗試進行一次深度優先搜索，如果搜索到1，就繼續向它的四周搜索。同時我們每找到一個1，就將其標為0，這樣就能把整個島嶼變成0。我們只要記錄對矩陣遍歷時能進入多少次搜索，就代表有多少個島嶼。

public class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        if(grid.length==0) return res;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j]=="1"){
                    searchIsland(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }
    
    private void searchIsland(char[][] grid, int i, int j){
        grid[i][j]="0";
        // 搜索該點連通的上下左右
        if(i>0 && grid[i-1][j]=="1") searchIsland(grid, i-1, j);
        if(j>0 && grid[i][j-1]=="1") searchIsland(grid, i, j-1);
        if(i
2018/2
class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        count = 0
        for row in range(0, len(grid)):
            for col in range(0, len(grid[0])):
                if grid[row][col] == "1":
                    self.exploreIsland(grid, row, col)
                    count += 1
        return count
                    
    
    def exploreIsland(self, grid, row, col):
        grid[row][col] = "0"
        if (row > 0 and grid[row - 1][col] == "1"):
            self.exploreIsland(grid, row - 1, col)
        if (col > 0 and grid[row][col - 1] == "1"):
            self.exploreIsland(grid, row, col - 1)
        if (row < len(grid) - 1 and grid[row + 1][col] == "1"):
            self.exploreIsland(grid, row + 1, col)
        if (col < len(grid[0]) - 1 and grid[row][col + 1] == "1"):
            self.exploreIsland(grid, row, col + 1)
2018/10
func explore(grid *[][]byte, row int, col int) {
    (*grid)[row][col] = "0"
    if row > 0 && (*grid)[row-1][col] == "1" {
        explore(grid, row-1, col)
    }
    if row < len((*grid))-1 && (*grid)[row+1][col] == "1" {
        explore(grid, row+1, col)
    }
    if col > 0 && (*grid)[row][col-1] == "1" {
        explore(grid, row, col-1)
    }
    if col < len((*grid)[0])-1 && (*grid)[row][col+1] == "1" {
        explore(grid, row, col+1)
    }
}

func numIslands(grid [][]byte) int {
    count := 0
    for i, row := range grid {
        for j, val := range row {
            if val == "1" {
                explore(&grid, i, j)
                count++
            }
        }

    }
    return count
}
后續 Follow Up
Q:如何找湖的數量呢？湖的定義是某個0，其上下左右都是同一個島嶼的陸地。
A:我們可以先用Number of island的方法，把每個島標記成不同的ID，然后過一遍整個地圖的每個點，如果是0的話，就DFS看這塊連通水域是否被同一塊島嶼包圍，如果出現了不同數字的陸地，則不是湖。
public class NumberOfLakes {
    
    public static void main(String[] args){
        NumberOfLakes nof = new NumberOfLakes();
        int[][] world = {{1,1,1,0,1},{1,0,0,1,0},{1,1,1,1,1,},{0,1,1,0,1},{0,1,1,1,1}};
        System.out.println(nof.numberOfLakes(world));
    }
    
    public int numberOfLakes(int[][] world){
        int islandId = 2;
        for(int i = 0; i < world.length; i++){
            for(int j = 0; j < world[0].length; j++){
                if(world[i][j] == 1){
                    findIsland(world, i, j, islandId);
                    islandId++;
                }
            }
        }
        int lake = 0;
        for(int i = 0; i < world.length; i++){
            for(int j = 0; j < world[0].length; j++){
                if(world[i][j] == 0){
                    // 找到當前水域的鄰接陸地編號
                    int currId = 0;
                    if(i > 0) currId = (world[i - 1][j] != 0 ? world[i - 1][j] : currId);
                    if(j > 0) currId = (world[i][j - 1] != 0 ? world[i][j - 1] : currId);
                    if(i < world.length - 1) currId = (world[i + 1][j] != 0 ? world[i + 1][j] : currId);
                    if(j < world[0].length - 1) currId = (world[i][j + 1] != 0 ? world[i][j + 1] : currId);
                    // 如果該點是湖，加1
                    if(findLake(world, i, j, currId)){
                        lake++;
                    }
                }
            }
        }
        return lake;
    }
    
    private boolean findLake(int[][] world, int i, int j, int id){
        // 將當前水域標記成周邊島嶼的數字
        world[i][j] = id;
        // 找上下左右是否是同一塊島嶼的陸地，如果是水域則繼續DFS，如果當前水域是邊界也說明不是湖
        boolean up = i != 0 
                && (world[i - 1][j] == id 
                || (world[i - 1][j] == 0 && findLake(world, i - 1, j, id)));
        boolean down = i != world.length - 1 
                && (world[i + 1][j] == id 
                || (world[i + 1][j] == 0 && findLake(world, i + 1, j, id)));
        boolean left = j != 0 
                && (world[i][j - 1] == id 
                || (world[i][j - 1] == 0 && findLake(world, i, j - 1, id)));
        boolean right = j != world[0].length - 1 
                && (world[i][j + 1] == id 
                || (world[i][j + 1] == 0 && findLake(world, i, j + 1, id)));
        return up && down && right && left;
    }
    
    private void findIsland(int[][] world, int i, int j, int id){
        world[i][j] = id;
        if(i > 0 && world[i - 1][j] == 1) findIsland(world, i - 1, j, id);
        if(j > 0 && world[i][j - 1] == 1) findIsland(world, i, j - 1, id);
        if(i < world.length - 1 && world[i + 1][j] == 1) findIsland(world, i + 1, j, id);
        if(j < world[0].length - 1 && world[i][j + 1] == 1) findIsland(world, i, j + 1, id);
    }
}