Max Area of Island
给一个grid里面是0和1, 求最大面积的1.
典型的搜索问题. 用-1标visitied.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
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; } } |