Original address: https://leetcode-cn.com/leetbook/read/queue-stack/kbcqv/

The problem is located in the queue, breadth first search under the learning problem.

The original title is as follows:

Here is a two-dimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid.

Islands are always surrounded by water, and each island can only be formed by adjacent land links in the horizontal and / or vertical directions.

In addition, you can assume that all four sides of the mesh are surrounded by water.

Example 1:

Input: grid =[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:

Input: grid =[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

Tips:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
The value of grid[i][j] is' 0 'or' 1 '

Although I have just learned the basic algorithms of queue, breadth first search and tree sequence traversal, I am still confused to see this problem. I have no idea. After trying for a long time, I read the idea of the solution and made sure that I understood the idea. Then I didn't read his code, so I tried to write the code according to this idea.
The code is as follows:

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;

	}
}

The result of this code must be correct, but the operation is not successful, and an error "out of time limit" is reported,
After repeated modifications, it still timed out, so I went to compare this code with the answers of people who have successfully run it. I found that the general ideas are almost the same, except for a very small, insignificant part that really affects the performance
When the number "up, down, left, right" is found to be 1, it should be set to 0 immediately. If it has to be set to 0 when looping to this position, then when it is not looped to this position, the position will appear repeatedly in the loop traversal with the value of 1, which is a very loss of performance.
So it's written as follows: (one line is deleted and four lines are added)

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;

}
}

In this way, the performance is improved.
So in the future, we should pay attention to the problem of whether or not we can and need to continue to participate in the next cycle, which is a link worthy of thinking about performance.
For the record.