Max Area Of Island Problem
Description
LeetCode Problem 695.
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
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0 or 1.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), ans = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) ans = max(ans, dfs(grid, i, j));
return ans;
}
private:
int dfs(vector<vector<int>>& grid, int row, int col) {
int m = grid.size(), n = grid[0].size(), area = 1;
grid[row][col] = 2;
vector<int> dir({-1,0,1,0,-1});
for (int i = 0; i < 4; i++) {
int r = row+dir[i], c = col+dir[i+1];
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1)
area += dfs(grid, r, c);
}
return area;
}
};