題目：200. Number of Islands

連結：https://leetcode.com/problems/number-of-islands/description/

• 等級：Medium

解題思路

• 將網格視為點：我們將網格想像為一堆點。 每個“1”單元就像一個點。
• 點分組：從一個「1」單元格開始，像探險家一樣，移動到其相鄰的點（帶有「1」的單元格）。 我們繼續這樣做，直到到達同一組（島）中的所有連接點。 使用一個特殊的清單來記住我們已經訪問過哪些點。
• 隊列幫助：為了有效地探索相鄰點，使用隊列。 將隊列視為一排等待檢查相鄰點的探索者。
• 尋找所有島嶼：我們對網格中的所有點重複此過程。 每次我們發現一個以前沒有訪問過的新的“1”單元格時，就從那裡開始探索。 透過這種方式追蹤所有獨立的島嶼。

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    RestOfLand(grid, i, j);
                }
            }
        }
        return count;
    }
    
    private void RestOfLand(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == '0') return;
        
        grid[i][j] = '0';
        RestOfLand(grid, i+1, j);
        RestOfLand(grid, i-1, j);
        RestOfLand(grid, i, j+1);
        RestOfLand(grid, i, j-1);
        return;
    }
}

• Time complexity: O(n^2)
• Space complexity: O(n^2)

題目：695. Max Area of Island

連結：https://leetcode.com/problems/max-area-of-island/description/

• 等級：Medium

class Solution {
    public int max = 0;
    public int sum = 0;
    public int maxAreaOfIsland(int[][] grid) {
        for(int i = 0; i<grid.length;i++)
        {
            for(int j = 0; j<grid[i].length;j++)
            {
                if(grid[i][j]!=0)
                {
                    sum = 0; 
                    dfs(grid,i,j);
                    max  = Math.max(max,sum);
                }
            }
        }

        return max;
    }

    private void dfs(int[][] grid ,int r ,int c)
    {
        if(r>=grid.length || c>=grid[0].length || r<0|| c<0 || grid[r][c]==0)
        {
            return ;
        }

        sum++;
        grid[r][c] = 0;
        dfs(grid,r,c+1);
        dfs(grid,r,c-1);
        dfs(grid,r+1,c);
        dfs(grid,r-1,c);
    }
}

• Time complexity: O(n^2)
• Space complexity: O(n^2)