Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Copy [[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]]
Copy class Solution {
public int maxAreaOfIsland(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
boolean[][] isVisited = new boolean[grid.length][grid[0].length];
int maxArea = 0;
for(int i = 0; i < grid.length ; i++){
for(int j = 0; j<grid[0].length; j++){
if(grid[i][j] == 1 && isVisited[i][j] == false){
isVisited[i][j] = true;
int area = bfs(grid,isVisited,i,j);
maxArea = Math.max(area,maxArea);
}
}
}
return maxArea;
}
public int bfs(int[][] grid, boolean[][] isVisited, int x,int y){
int[] xdir = {1,0,-1,0};
int[] ydir = {0,1,0,-1};
int area = 1;
Queue<Integer> queue = new LinkedList<>();
queue.offer(x);
queue.offer(y);
while(!queue.isEmpty()){
int cx = queue.poll();
int cy = queue.poll();
for(int i = 0; i < 4; i++){
int nx = cx+xdir[i];
int ny = cy + ydir[i];
if(isInBound(grid,nx,ny) && isVisited[nx][ny] == false && grid[nx][ny] == 1){
isVisited[nx][ny] = true;
area++;
queue.offer(nx);
queue.offer(ny);
}
}
}
return area;
}
public boolean isInBound(int[][] grid, int x,int y){
if( x< 0 || x >= grid.length || y <0 || y >= grid[0].length){
return false;
}
return true;
}
}