LeetCode - Max Area of Island
2024-10-19 11:39:09
Given a non-empty 2D array grid of 0's and 1's, 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. Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.) Example 1:
[[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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
BFS + 涂色法:
class Solution {
public int maxAreaOfIsland(int[][] grid) {
if(grid == null){
return 0;
}
int row = grid.length;
int column = grid[0].length;
int max = 0;
for(int i = 0; i<row; i++){
for(int j = 0; j<column; j++){
if(grid[i][j] == 1){
//count++;
//grid[i][j] = 2;
Queue<int[]> queue = new LinkedList<>();
int count = 0;
queue.add(new int[]{i,j});
grid[i][j] = 2;
while(!queue.isEmpty()){
int[] temp = queue.poll();
int r = temp[0];
int c = temp[1];
count++;
//move up
if(r - 1 >= 0 && grid[r - 1][c] == 1){
queue.add(new int[]{r-1, c});
grid[r-1][c] = 2;
}
//move down
if(r + 1 < row && grid[r + 1][c] == 1){
queue.add(new int[]{r+1, c});
grid[r+1][c] = 2;
}
//move left
if(c - 1 >= 0 && grid[r][c - 1] == 1){
queue.add(new int[]{r, c-1});
grid[r][c-1] = 2;
}
//move right
if(c + 1 < column && grid[r][c + 1] == 1){
queue.add(new int[]{r, c+1});
grid[r][c+1] = 2;
}
}
if(count>max){
max = count;
}
} }
}
return max;
}
}
最新文章
- 创建ASP.NET Core MVC应用程序(6)-添加验证
- c#.netGr idView1在div不局中
- recv和send函数
- Careercup - Facebook面试题 - 5344154741637120
- DOCTYPE html PUBLIC 指定了 HTML 文档遵循的文档类型定义
- UEFI GPT
- bzoj2100 [Usaco2010 Dec]Apple Delivery
- diff命令
- 『算法』Dinic求最大流
- javascript高级排序算法之快速排序(快排)
- input在ios safari中的内阴影解决方法
- edu30F. Forbidden Indices
- Web Service 与WebAPI 的区别
- CSS3:文字属性
- poj2299树状数组入门,求逆序对
- 2016NOI冬令营day5
- 20155211实验2 Windows口令破解
- ExpandoObject使用
- BZOJ1879:[SDOI2009]Bill的挑战(状压DP)
- OPENCV VS设置