https://leetcode.com/problems/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
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.
- code bfs
class Solution {
private final static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int maxAreaOfIsland(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int maxarea = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
maxarea = Math.max(bfs(grid, i, j, rows, cols), maxarea);
}
}
}
return maxarea;
}
public int bfs(int[][] grid, int x, int y, int rows, int cols) {
Queue<int[]> q = new LinkedList<>();
int count = 0;
grid[x][y] = 0;
q.add(new int[]{x, y});
while (!q.isEmpty()) {
count++;
int[] cur = q.poll();
int row = cur[0];
int col = cur[1];
for (int[] dir : dirs) {
int nx = row + dir[0];
int ny = col + dir[1];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {
q.add(new int[]{nx, ny});
grid[nx][ny] = 0;
}
}
}
return count;
}
}
- code dfs
class Solution {
public int[][] curGrid;
public int[][] directions = {{0,1}, {0, -1}, {1, 0}, {-1, 0}};
public int m, n;
public int maxAreaOfIsland(int[][] grid) {
// curGrid = Arrays.stream(grid).map(a -> Arrays.copyOf(a, a.length)).toArray(int[][]::new);
curGrid = grid;
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int row = 0; row < m; row++){
for (int col = 0; col < n; col++){
if (curGrid[row][col] == 1){
maxArea = Math.max(maxArea, dfs(row, col));
}
}
}
return maxArea;
}
public int dfs(int i, int j){
if (i < 0 || i >= m || j < 0 || j >= n || curGrid[i][j] != 1){
return 0;
}
curGrid[i][j] = 2;
int curArea = 1;
for (int[] d: directions){
int nx = i + d[0];
int ny = j + d[1];
curArea += dfs(nx, ny);
}
return curArea;
}
}