アルゴリズム_島の面積

733. アルゴリズム_島の最大面積#

m x n のバイナリマトリックスグリッドが与えられます。島とは、4 方向（水平または垂直）で接続された 1 のグループ（陸地を表す）です。グリッドの 4 つの端は水に囲まれていると仮定できます。

島の面積は、島にある値が 1 のセルの数です。

グリッド内の島の最大面積を返します。島が存在しない場合は、0 を返します。

例 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: 答えは11ではなく、島は4方向で接続されている必要があります。

例 2:

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

解法#

FloodFill アルゴリズムに似ていますが、ここでは隣接するセルを同じ色に変更するのではなく、隣接する 1 の数を計算します。解法は、配列を遍歴し、現在の要素が 1 であれば、この要素の周囲の 1 の数を計算します —— 再帰を通じて、隣接要素の値を取得し、1 の数を加算し、現在の要素を 0 に変更して重複計算を避けます。

コードは以下の通りです：


class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        var maxArea = 0
        for i in 0..<grid.count {
            for j in 0..<grid[i].count {
                if grid[i][j] == 1 {
                    // 現在が1の場合、周囲の1の総数を計算
                    var newGrid = grid
                     maxArea = max(maxArea, calculateMaxArea(&newGrid, i, j))
                }
            }
        }
        return maxArea
    }
    
    func calculateMaxArea(_ grid: inout [[Int]], _ i: Int, _ j: Int) -> Int {
        if i >= 0 && i < grid.count && j >= 0 && j < grid[i].count && grid[i][j] == 1 {
            grid[i][j] = 0
            return 1 + calculateMaxArea(&grid, i-1, j) + calculateMaxArea(&grid, i+1, j) + calculateMaxArea(&grid, i, j-1) + calculateMaxArea(&grid, i, j+1)
        }
        return 0
    }
}