问题描述
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.
问题分析
问题比较简单，利用dfs遍历即可；代码如下
示例代码
var (
directions = [][]int{
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
}
visited []int
)
func maxAreaOfIsland(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
// 一维数组标识是否访问过
visited = make([]int, rows*cols)
ans := 0
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
ans = max(ans, dfs(grid, visited, row, col, rows, cols))
}
}
return ans
}
func dfs(grid [][]int, visited []int, row int, col int, rows int, cols int) int {
if visited[row*cols+col] > 0 {
return 0
}
// mark as visited
visited[row*cols+col] = 1
if grid[row][col] == 0 {
return 0
}
area := 1
for _, v := range directions {
newrow := row + v[0]
newcol := col + v[1]
// 边界条件
if newrow < 0 || newrow >= rows || newcol < 0 || newcol >= cols {
continue
}
area += dfs(grid, visited, row+v[0], col+v[1], rows, cols)
}
return area
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}