Brooke

一、題目

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.

 

二、程式作法

/*寫法一*/
public class Solution
{
    int maxArea = 0;
    bool[,] chk = { };
    int[][] grid = Array.Empty<int[]>();
    public int MaxAreaOfIsland(int[][] grid)
    {
        chk = new bool[grid.Length, grid[0].Length];
        this.grid = grid;

        for (int i = 0; i < grid.Length; i++)
            for (int j = 0; j < grid[0].Length; j++)
                maxArea = Math.Max(maxArea, CheckIsland(i, j));

        return maxArea;
    }

    public int CheckIsland(int sr, int sc)
    {
        if (sr < 0 || sr > grid.Length - 1 || sc < 0 || sc > grid[0].Length - 1)
            return 0;

        if (chk[sr, sc] == false && grid[sr][sc] == 1)
        {
            chk[sr, sc] = true;
            return CheckIsland(sr - 1, sc) + CheckIsland(sr + 1, sc) + CheckIsland(sr, sc - 1) + CheckIsland(sr, sc + 1) + 1;
        }
        else
        {
            chk[sr, sc] = true;
            return 0;
        }
    }
}

/*寫法二*/
/*
public class Solution
{
    int[][] grid = Array.Empty<int[]>();
    bool[,] seen = new bool[0, 0] { };

    public int MaxAreaOfIsland(int[][] grid)
    {
        this.grid = grid;

        int m = grid.Length;
        int n = grid[0].Length;
        seen = new bool[m, n];
        int maxArea = 0;

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == 1 && seen[i, j] == false)
                {
                    maxArea = Math.Max(maxArea, CheckArea(i, j));
                }
            }
        }

        return maxArea;
    }

    public int CheckArea(int sr, int sc)
    {
        int area = 1;
        seen[sr, sc] = true;

        //上
        if (sr - 1 >= 0 && grid[sr - 1][sc] == 1 && seen[sr - 1, sc] == false)
        {
            area += CheckArea(sr - 1, sc);
        }

        //下
        if (sr + 1 < grid.Length && grid[sr + 1][sc] == 1 && seen[sr + 1, sc] == false)
        {
            area += CheckArea(sr + 1, sc);
        }

        //左
        if (sc - 1 >= 0 && grid[sr][sc - 1] == 1 && seen[sr, sc - 1] == false)
        {
            area += CheckArea(sr, sc - 1);
        }

        //右
        if (sc + 1 < grid[sr].Length && grid[sr][sc + 1] == 1 && seen[sr, sc + 1] == false)
        {
            area += CheckArea(sr, sc + 1);
        }

        return area;
    }
}
*/

 

三、思路筆記

給定一個矩陣，值為0表示海水，值為1表示島嶼，找出面積最大的島嶼。

應用 Depth-First Search

一個 m x n 的矩陣，一開始就每一點去檢查是否為島嶼，

如果是的話，則開始去檢查相鄰的點是否為島嶼，

並回傳與紀錄，比出目前最大島嶼面積，進而找出最大島嶼。