原题：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
给你一个由 ‘1‘（陆地）和 ‘0‘（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题思路：
我采用的方式类似于广度遍历的方式。如果该位置是 ‘1’ 则入队，然后判断其上下左右是否为 ‘1’ ，1入队，0不操作。然后出队。通过循环可以找到连接的岛屿。在入队的同时将该位置重置为‘0’
具体代码如下
public int numIslands(char[][] grid) { int num=0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[i].length;j++){ if(grid[i][j]==‘1‘){ num++; Queue<String> queue=new LinkedList<String>(); queue.offer(i+";"+j); //起始节点入队 ，根据角标设定 i;j 的格式，i为行，j为列入队 grid[i][j]=‘0‘; //该位置 重定为0 while(!queue.isEmpty()){ //开始广度遍历 String t=queue.peek(); //取队头 queue.poll(); //出队 int hang=Integer.parseInt(t.split(";")[0]); //取出行数 int lie=Integer.parseInt(t.split(";")[1]); //取出列数
//判断该点的上下左右 if(hang>0&&grid[hang-1][lie]==‘1‘) {//上 queue.offer((hang - 1) + ";" + lie); grid[hang-1][lie]=‘0‘; } if(hang<grid.length-1&&grid[hang+1][lie]==‘1‘) {//下 queue.offer((hang + 1) + ";" + lie); grid[hang+1][lie]=‘0‘; } if(lie>0&&grid[hang][lie-1]==‘1‘) {//左 queue.offer(hang + ";" + (lie - 1)); grid[hang][lie - 1] = ‘0‘; } if(lie<grid[0].length-1&&grid[hang][lie+1]==‘1‘) {//右 queue.offer(hang + ";" + (lie + 1)); grid[hang][lie + 1] = ‘0‘; } } } } } return num; }
PS：目前该解法时间复杂度和空间复杂度相对较高。
如有错误，欢迎指正。
原文：https://www.cnblogs.com/wys-373/p/13210467.html