Max Area of Island
给一个grid里面是0和1, 求最大面积的1.
典型的搜索问题. 用-1标visitied.
class Solution {
class Pair{
int a;
int b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1){
res = Math.max(res, bfs(grid, i, j));
}
}
}
return res;
}
public int bfs(int[][] g, int row, int col) {
int res = 1;
g[row][col] = -1;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(row, col));
int[][] dirs = new int[][]{
{0,1},
{-1,0},
{1,0},
{0,-1}
};
while(!q.isEmpty()){
Pair p = q.poll();
for(int[] d : dirs) {
int newRow = p.a + d[0];
int newCol = p.b + d[1];
if(0 <= newRow && newRow < g.length && 0 <= newCol && newCol < g[0].length && g[newRow][newCol] == 1){
res++;
g[newRow][newCol] = -1;
q.add(new Pair(newRow, newCol));
}
}
}
return res;
}
}