【力扣200. 岛屿数量】的一种错误解法（BFS）

先看正确解法，每个节点1一旦被访问到，就立刻被改为0

classSolution{public:intnumIslands(vector<vector<char>>&grid){intm=grid.size();if(0==m)return0;intn=grid[0].size();if(0==n)return0;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if('0'==grid[i][j])continue;grid[i][j]='0';count++;queue<pair<int,int>>q;// 相邻节点q.push({i,j});while(false==q.empty()){pair<int,int>p=q.front();q.pop();intx=p.first;inty=p.second;if(x-1>=0&&grid[x-1][y]=='1'){q.push({x-1,y});grid[x-1][y]='0';}if(x+1<m&&grid[x+1][y]=='1'){q.push({x+1,y});grid[x+1][y]='0';}if(y-1>=0&&grid[x][y-1]=='1'){q.push({x,y-1});grid[x][y-1]='0';}if(y+1<n&&grid[x][y+1]=='1'){q.push({x,y+1});grid[x][y+1]='0';}}}}returncount;}};

下面的错误解法，在出队后统一将访问的节点值改为0

classSolution{public:intnumIslands(vector<vector<char>>&grid){intm=grid.size();if(0==m)return0;intn=grid[0].size();if(0==n)return0;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if('0'==grid[i][j])continue;// grid[i][j] = '0';count++;queue<pair<int,int>>q;// 相邻节点q.push({i,j});while(false==q.empty()){pair<int,int>p=q.front();q.pop();intx=p.first;inty=p.second;grid[x][y]='0';if(x-1>=0&&grid[x-1][y]=='1'){q.push({x-1,y});// grid[x - 1][y] = '0';}if(x+1<m&&grid[x+1][y]=='1'){q.push({x+1,y});// grid[x + 1][y] = '0';}if(y-1>=0&&grid[x][y-1]=='1'){q.push({x,y-1});// grid[x][y - 1] = '0';}if(y+1<n&&grid[x][y+1]=='1'){q.push({x,y+1});// grid[x][y + 1] = '0';}}}}returncount;}};

这种错误做法有一个逻辑问题：没有立即标记访问过的节点，这会导致重复入队和无限循环。

问题分析

在将节点加入队列时不立即标记为已访问，会发生以下情况：

// 错误示例if(x-1>=0&&grid[x-1][y]=='1'){q.push({x-1,y});// 这里push了(x-1, y)// 没有立即标记为'0'，这个节点还是'1'}

具体问题

假设有这样的岛屿：

1 1 1 1

执行流程：

1. 遇到(0,0)，入队(0,0)
2. 弹出(0,0)，访问它的四个方向
3. 发现(0,1)是1，入队(0,1)← 入队时没有标记
4. 发现(1,0)是1，入队(1,0)← 入队时没有标记
5. 弹出(0,1)，访问四个方向
6. 发现(0,0)已经是0，没问题
7. 发现(1,1)是1，入队(1,1)
8. 弹出(1,0)，访问四个方向
9. 发现(0,0)已经是0
10. 发现(1,1)是1←问题在这里！

由于之前(1,1)已经被发现但还没有被标记为0，当从(1,0)访问(1,1)时，又会入队一次(1,1)，导致重复入队。

更严重的问题

考虑更大的岛屿，这种重复入队会导致队列中包含大量重复节点，可能导致：

1. 队列过大
2. 处理时间增加
3. 在极端情况下可能导致无限循环或性能问题

正确做法

在节点入队时立即标记为已访问，这样：

1. 保证每个节点只入队一次
2. 避免重复访问
3. 逻辑更清晰，符合BFS的原则

// 正确做法：入队时立即标记if(x-1>=0&&grid[x-1][y]=='1'){q.push({x-1,y});grid[x-1][y]='0';// 立即标记}

或者也可以在弹出节点时标记，但这样需要在入队时检查是否已访问，而上述错误代码只在入队时检查grid[x - 1][y] == '1'，没有检查是否已经在队列中但还未被处理。