题目：岛屿数量 middle
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入: [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出: 1
示例 2:
输入: [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
思路： 1.经典的bfs
2.dfs也行
package leetCode.BFS; import java.util.ArrayDeque; import java.util.Arrays; public class lc_bfs_200_numIslands { public int numIslands(char[][] grid) { //四个方向 int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; //记录第几片岛屿 char count = '1'; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { //从'2'开始计数，若从1开始，bfs时会循环将已经加入queue的'1'再次加入（因为加入的条件为=1） count++; //每次bfs都将确定一片岛屿，即在网格上属于标记同一片岛屿 bfs(grid, dir, count, i, j); } } } //由于从2开始计数，所以要-1 return count - '0' - 1; } // 在网格上属于标记同一片岛屿，用同一个字符表示，从'2'开始 private void bfs(char[][] grid, int[][] dir, char count, int i, int j) { ArrayDeque<int[]> queue = new ArrayDeque<>(); grid[i][j] = count; queue.offer(new int[]{i, j}); while (!queue.isEmpty()) { //当前点 int[] point = queue.poll(); //遍历四个方向 for (int k = 0; k < dir.length; k++) { //每个方向的x,y坐标 int x = point[0] + dir[k][0]; int y = point[1] + dir[k][1]; //不越界且为‘1’时（即为陆地），加入queue并将其置为同一片岛屿，即第count片岛屿 if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == '1') { queue.offer(new int[]{x, y}); grid[x][y] = count; } } } } }
