Algorithem_Max Area of Island

2022-04-20

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:

1
2
3

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:

1 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
    }
}