#200. Number of Islands

題目描述

給你一個m x n的2D二元格子grid作為一張地圖以1表示為陸地，0表示為水，回傳島嶼的數量。

島嶼的定義是周圍環繞著水，並且由相鄰的陸地連接而組成。

題目假設四個邊界都是環繞著水的。

限制條件

1. m == grid.length
2. n == grid[i].length
3. 1 <= m, n <= 300
4. grid[i][j] 只會是 '0' 或 '1'。

解題思路

我們分為以下幾個步驟來處理。

1. 找到島嶼。
2. 找到島嶼後先確認是否標記過。
3. 沒有標記過的島嶼，標記它的範圍並且島嶼數量計數加1。

public class Solution {
    public int NumIslands(char[][] grid) {
        int numsOfIsland=0;
        var visited = new HashSet<(int,int)>();
        for(int i=0;i<grid.Length;i++){
            for(int j=0;j<grid[i].Length;j++){
                if(grid[i][j]=='1'){
                    if(visited.Contains((i,j))) continue;
                    MarkIsland(grid,i,j,visited);
                    numsOfIsland++;
                }
            }
        }   
        return numsOfIsland;
    }    
    public void MarkIsland(char[][] grid, int x,int y, HashSet<(int,int)> visited){        
        if(visited.Contains((x,y))) return;
        if(grid[x][y]=='0') return;
        visited.Add((x,y));
        if(InBound(grid,x+1,y)) MarkIsland(grid,x+1,y,visited);
        if(InBound(grid,x-1,y)) MarkIsland(grid,x-1,y,visited);
        if(InBound(grid,x,y+1)) MarkIsland(grid,x,y+1,visited);
        if(InBound(grid,x,y-1)) MarkIsland(grid,x,y-1,visited);
    }
    public bool InBound(char[][] grid, int x,int y){
        return x>=0 && x<grid.Length && y>=0 && y<grid[0].Length;
    }
}

複雜度分析：

• 時間複雜度：O(m*n)。
• 空間複雜度：O(m*n)。

學習重點

• DFS
• BFS