###### tags: `Leetcode` `medium` `dfs` `bfs` `python` `c++` `Top 100 Liked Questions`

# 200. Number of Islands

## [題目連結:] https://leetcode.com/problems/number-of-islands/description/

## 題目:
Given an ```m x n``` 2D binary grid ```grid``` which represents a map of ```'1'```s (land) and ```'0'```s (water), return 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: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

**Example 2:**

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

## 解題想法:
* 題目為，求島嶼數量
* 1為陸地
* 0為海水
* 陸地週圍全是0才是島嶼

* 想法:
* 遍歷矩陣，每次遇到1，表示為新島，結果+1
* 並對其進行遞迴便利將其相鄰的1格子全變0

## Python: 遞迴

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res=0
        m=len(grid)
        n=len(grid[0])
        def clearIsland(i,j):
            '''
            判斷式不能寫:
            if 0<=i<m and 0<=j<n and grid[i][j]=='1':
                grid[i][j]='0'
            因為這樣就算出界，還是會繼續跑下面的遞迴
            會maximum recursion depth exceeded
            '''
            #check是否出界
            if i>=m or i<0 or j<0 or j>=n or grid[i][j]=='0':
                return
            #將該格更新為0    
            grid[i][j]='0'
            #並將其1的鄰居也做dfs改成0
            clearIsland(i+1,j)
            clearIsland(i-1,j)
            clearIsland(i,j+1)
            clearIsland(i,j-1)    
        
        for i in range(m):
            for j in range(n):
                if grid[i][j]=='1':
                    res+=1
                    clearIsland(i,j)
        return res

if __name__=='__main__':
    result = Solution()
    grid = [
        ["1","1","0","0","0"],
        ["1","1","0","0","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]
    ]
    ans = result.numIslands(grid)
    print(ans) #3

## Python: BFS

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res=0
        m=len(grid)
        n=len(grid[0])
        visited=[[False for _ in range(n)] for _ in range(m)]
        dirs=[(1,0),(-1,0),(0,1),(0,-1)]
        que=[]
        for i in range(m):
            for j in range(n):
                #若是海水or已拜訪過 則跳過
                if grid[i][j]=='0' or visited[i][j]==True:
                    continue
                else:
                    res+=1
                    que.append((i,j))
                    visited[i][j]=True
                    while que:
                        curX,curY = que.pop(0)
                        #改為0且拜訪過
                        grid[curX][curY]='0'
                        #遍歷週圍鄰居
                        for dirX,dirY in dirs:
                            tmpX=curX+dirX
                            tmpY=curY+dirY
                            if 0<=tmpX<m and 0<=tmpY<n and grid[tmpX][tmpY]=='1' and visited[tmpX][tmpY]==False:
                                que.append((tmpX,tmpY))
                                visited[tmpX][tmpY]=True
        return res

## C++: 遞迴

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int res=0;
        for (int i=0; i<m; i++){
            for (int j=0; j<n; j++){
                if (grid[i][j]=='0')
                    continue;
                else{
                    res+=1;
                    clearIsland(grid,m,n,i,j);
                }
            }
        }
        return res;
    }
    void clearIsland(vector<vector<char>>& grid, int m, int n, int i, int j){
        if (i>=m || i<0 || j>=n || j<0 || grid[i][j]=='0')
            return;
        grid[i][j]='0';
        clearIsland(grid,m,n,i+1,j);
        clearIsland(grid,m,n,i-1,j);
        clearIsland(grid,m,n,i,j+1);
        clearIsland(grid,m,n,i,j-1);
    }
};

int main(){
    vector<vector<char>> grid={
        {'1','1','0','0','0'},
        {'1','1','0','0','0'},
        {'0','0','1','0','0'},
        {'0','0','0','1','1'}
    };
    Solution res;
    int ans=res.numIslands(grid);
    cout<<ans<<endl;
    return 0;
}