BFS 爆TLE&MLE的教训

首先我们知道，BFS理论上每个点只需要判断一次就行（每一步标记已经扫过的点），时间复杂度和空间复杂度应该不会超O(n)，那么为什么还会产生TLE或者MLE的结果呢？请看下面的分析：

• TLE：我在这道题上出现TLE错误的主要原因是对于将标记位设置为1的时间不对。对于符合条件且未扫描过的点，我们需要进行入队的操作，并且在执行这一个入队操作的同时就应该将这个点的标志位设置为1，而不应该在将一个点从队首取出时再设置为1.如果采用后面的方法，就可能导致符合条件的点入队了多次的情况发生。
• MLE:结合上面TLE产生的原因，不难推知如果有过多的相同结点入队，将造成极大的冗余，进而产生MLE的错误。\ 综上，BFS产生TLE或者MLE错误时，可以检查一下在结点入队之前是否已经将其标记。

• 附上两种形式的代码供大家参考

  
  while(!q.empty()){
  
  node fro=q.front();
  q.pop();
  vis[q.x][q.y]=1;
  
  .....
  }

while(!q.empty()){

if(check(x,y)){

     vis[x][y]=1;
     node tmp;
     tmp.x=x,tmp.y=y;
     q.push(tmp);

}

}