leetcode热题岛屿数量
给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ]输出：1
示例 2：
输入：grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]输出：3
/** * 深度优先求岛屿个数 * @param grid * @return */ public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { deleteSideOne(grid,i,j); count++; } } } return count; } /** * 广度优先岛屿个数 * @param grid * @return */ public int numIslands1(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { deleteSideOneDfs(grid,i,j); count++; } } } return count; } private void deleteSideOneDfs(char[][] grid, int i, int j) { Queue<int[]> list = new LinkedList<>(); list.add(new int[] {i,j}); if (!list.isEmpty()) { int[] cur = list.remove(); i = cur[0];j = cur[1]; if (inArea(grid,i,j) && grid[i][j] == '1') { grid[i][j] = '0'; list.add(new int[] {i+1,j}); list.add(new int[] {i-1,j}); list.add(new int[] {i,j+1}); list.add(new int[] {i,j-1}); } } } private void deleteSideOne(char[][] grid, int i, int j) { if (!inArea(grid,i,j) || grid[i][j] == '0') { return; } // 此时 = ‘1’ grid[i][j] = '0'; deleteSideOne(grid,i,j-1); deleteSideOne(grid,i,j+1); deleteSideOne(grid,i-1,j); deleteSideOne(grid,i+1,j); } /** * 岛屿的最大面积 * @param grid * @return */ 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) { int tempA = area(grid,i,j); res = Math.max(res,tempA); } } } return res; } private int area(int[][] grid, int i, int j) { // 超出网格，返回0 if (!inArea(grid, i, j)) { return 0; } // 如果不是岛屿，返回0 if (grid[i][j] != 1) { return 0; } // 递归计算相邻的是否岛屿(加上相邻的面积) return 1 + area(grid, i - 1, j) + area(grid, i + 1, j) + area(grid, j, j - 1) + area(grid, i, j + 1); } private boolean inArea(int[][] grid, int i, int j) { return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length; } private boolean inArea(char[][] grid, int i, int j) { return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length; }