原题地址：https://leetcode-cn.com/leetbook/read/queue-stack/kbcqv/
该题是位于，队列、广度优先搜索的学习下的题。
原题如下：
给你一个由 ‘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
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’
虽然刚学了队列、广度优先搜索、树的层序遍历等基础算法，但看到这个题还是懵了。毫无思路，尝试了很久之后，看了解答的思路，确定看懂了思路，然后没有看他的解题代码，自己尝试按照这个思路去写代码。
写出的代码如下：
class Solution {
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++){
char curRoot=grid[i][j];
if(curRoot=='1')
{
Queue<Integer> ijQueue=new LinkedList<>();
ijQueue.add(i*grid[0].length+j);
count++;
while(!ijQueue.isEmpty()){
Integer index = ijQueue.poll();
int k=index/grid[0].length;
int l=index%grid[0].length;
grid[k][l]='0';
if (k!=0&&grid[k-1][l]=='1') {
//up
ijQueue.add((k-1)*grid[0].length+l);
}
if (k!=grid.length-1&&grid[k+1][l]=='1') {
//down
ijQueue.add((k+1)*grid[0].length+l);
}
if (l!=0&&grid[k][l-1]=='1') {
//left
ijQueue.add(k*grid[0].length+(l-1));
}
if (l!=grid[0].length-1&&grid[k][l+1]=='1') {
//right
ijQueue.add(k*grid[0].length+(l+1));
}
}
}
}
}
return count;
}
}
这个代码结果一定是对的，但运行不成功，报错”超出时间限制“，
反复修改之后还是超时，于是我去将这份代码对比已经运行成功的人的答案，发现大体思路都差不多，差在了一个很小的，很不起眼，但是真的很影响性能的部分：
在找到”上下左右“数字为1时，就应该立即设为0，如若非要在循环到这个位置时才设为0，那么当没有循环到这个位置时，就会以1的值重复将该位置出现在循环遍历之中，这是非常损耗性能的做法。
于是改为如下写法：（删掉了一行，增加了四行）
class Solution {
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++){
char curRoot=grid[i][j];
if(curRoot=='1')
{
grid[i][j]=0;
Queue<Integer> ijQueue=new LinkedList<>();
ijQueue.add(i*grid[0].length+j);
count++;
while(!ijQueue.isEmpty()){
Integer index = ijQueue.poll();
int k=index/grid[0].length;
int l=index%grid[0].length;
if (k!=0&&grid[k-1][l]=='1') {
//up
grid[k-1][l]='0';
ijQueue.add((k-1)*grid[0].length+l);
}
if (k!=grid.length-1&&grid[k+1][l]=='1') {
//down
grid[k+1][l]='0';
ijQueue.add((k+1)*grid[0].length+l);
}
if (l!=0&&grid[k][l-1]=='1') {
//left
grid[k][l-1]='0';
ijQueue.add(k*grid[0].length+(l-1));
}
if (l!=grid[0].length-1&&grid[k][l+1]=='1') {
//right
grid[k][l+1]='0';
ijQueue.add(k*grid[0].length+(l+1));
}
}
}
}
}
return count;
}
}
这样一来，性能就提上来了。
所以以后要注意一个问题，循环到的值，可不可以、有没有必要继续参与接下来的循环当中，是一个关于性能的值得思考的环节。
谨以此记录。