733. アルゴリズム_島の最大面積#
m x n のバイナリ行列 grid が与えられます。島は、4 方向（水平または垂直）に接続された 1（陸地を表す）のグループです。グリッドの四つの辺はすべて水で囲まれていると仮定しても構いません。
島の面積は、島内の値が 1 のセルの数です。
グリッド内の島の最大面積を返します。島が存在しない場合は、0 を返します。
例 1:
入力: 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]]
出力: 6
説明: 答えは11ではありません、なぜなら島は4方向に接続されている必要があるからです。
例 2:
入力: grid = [[0,0,0,0,0,0,0,0]]
出力: 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
}
}