| 23 | class Solution { |
| 24 | // DFS and you can implement BFS with queue |
| 25 | public int maxAreaOfIsland(int[][] grid) { |
| 26 | int[] dr = new int[]{1, -1, 0, 0}; |
| 27 | int[] dc = new int[]{0, 0, 1, -1}; |
| 28 | int ans = 0; |
| 29 | for (int r0 = 0; r0 < grid.length; r0++) { |
| 30 | for (int c0 = 0; c0 < grid[0].length; c0++) { |
| 31 | if (grid[r0][c0] == 1) { |
| 32 | int shape = 0; |
| 33 | Stack<int[]> stack = new Stack(); |
| 34 | stack.push(new int[]{r0, c0}); |
| 35 | grid[r0][c0] = 0; |
| 36 | while (!stack.empty()) { |
| 37 | int[] node = stack.pop(); |
| 38 | int r = node[0], c = node[1]; |
| 39 | shape++; |
| 40 | for (int k = 0; k < 4; k++) { |
| 41 | int nr = r + dr[k]; |
| 42 | int nc = c + dc[k]; |
| 43 | if (0 <= nr && nr < grid.length && |
| 44 | 0 <= nc && nc < grid[0].length && |
| 45 | grid[nr][nc] == 1) { |
| 46 | stack.push(new int[]{nr, nc}); |
| 47 | grid[nr][nc] = 0; |
| 48 | } |
| 49 | } |
| 50 | } |
| 51 | ans = Math.max(ans, shape); |
| 52 | } |
| 53 | } |
| 54 | } |
| 55 | return ans; |
| 56 | } |
| 57 | } |