---
# System prepended metadata

title: Leetcode 200. Number of Islands
tags: [Leetcode(C++)]

---

# Leetcode 200. Number of Islands
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/number-of-islands/ 。

想法 : 

    flood fill。
    掃描到有島就把島歸0，再繼續找下一座島。

時間複雜度 : O(m*n)。

程式碼 :

```
class Solution {
public:
    int maxr, maxc, ans;
    
    void erase(vector<vector<char>>& grid, int r,int c){
        if(grid[r][c] == '1'){
            grid[r][c]='0';
            
            if(r <= maxr-2) erase(grid, r+1, c);
            if(r >= 1)   erase(grid, r-1, c);
            if(c <= maxc-2) erase(grid, r, c+1);
            if(c >= 1)   erase(grid, r, c-1);
        }
    }
    
    int numIslands(vector<vector<char>>& grid) {
        maxr=grid.size(); 
        maxc=grid[0].size();
        ans=0;
        
        for(int i=0 ; i<maxr ; i++){
            for(int j=0 ; j<maxc ; j++){
                if(grid[i][j] == '1'){
                    erase(grid, i, j);
                    ans++;
                }
            }
        }
        
        return ans;
    }
};
```