[LeetCode刷題筆記] 695 – Max Area of Island

題目描述：

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

題解（DFS）：

這題給了我們一個交錯數組，在這個數組中，1代表陸地，0代表海洋。如果有一片陸地互相接攘（陸地數>=1），並被海洋所包圍，則可稱為一個小島。問這個數組中，面積最大的島嶼面積大小，也就是數組中有最多相互連接的1的區域中，1的數量有多少。

這個題的解題思路是非常典型的深度搜索。創建一個isVisited的bool類型二維數組標志已經搜索過的區域，然後用兩重循環來遍歷整個交錯數組，對每個元素嘗試進行深度搜索。如果當前行列索引超出邊界/不是陸地（grid[row][col] == 0）/已經被搜索過，都直接返回。而找到陸地時，則對陸地的周邊區域通過遞歸進行DFS，直到檢查完所有相鄰的陸地，返回該「小島」的陸地面積。

然後在兩層循環中持續利用Math.Max來維護一個「最大陸地面積」的值，最後循環結束後返回的值就是本題的答案。

public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        int row = grid.Length;
        int col = grid[0].Length;
        
        bool[,] isVisited = new bool[row, col];
        
        int result = 0;
        for(int y = 0; y < row; y++)
        {
            for(int x = 0; x < col; x++)
            {
                result = Math.Max(result, IslandCounter(grid, isVisited, y, x));
            }
        }        
        
        return result;
    }
    
    int IslandCounter(int[][] grid, bool[,] isVisited, int currRow, int currCol)
    {
        int rowEdge = grid.Length;
        int colEdge = grid[0].Length;
        
        //Edge Judge
        if(currRow < 0 || currRow >= rowEdge || currCol < 0 || currCol >= colEdge) { return 0; }
        
        if(grid[currRow][currCol] == 0) { return 0; }
        
        //isVisited Judge
        if(isVisited[currRow, currCol]) { return 0; }
        
        //Make this be visited
        isVisited[currRow, currCol] = true;
        
        //DFS 4 dirs grid
        //Up
        int upCnt = IslandCounter(grid, isVisited, currRow - 1, currCol);
        //Down
        int downCnt = IslandCounter(grid, isVisited, currRow + 1, currCol);
        //Left
        int leftCnt = IslandCounter(grid, isVisited, currRow, currCol - 1);
        //Right
        int rightCnt = IslandCounter(grid, isVisited, currRow, currCol + 1);
            
        return 1 + upCnt + downCnt + leftCnt + rightCnt;
    }
}