733. Algorithem_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
解法#
和 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
}
}