最近在做一本通网站上1254题，犯了一个让我郁闷的错。之所以让我郁闷，是因为程序在打样例的时候能过，提交到服务器就两个点过，其余8个点都是运行错误，我花了很久才发现错在哪，也让后来的朋友不犯同样的错，特写此博文，如有不妥之处，请指教，本人不胜感激。先看问题、结果和源代码
程序源代码如下：
#include<bits/stdc++.h> using namespace std; int const mx=102; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int a[mx][mx],que[mx*mx][2],ans,dp[mx][mx],ha,la,hb,lb; void bfs() { int h=0,t=0,cx,cy,tx,ty; que[0][0]=ha,que[0][1]=la; while(h<=t) { cx=que[h][0],cy=que[h++][1]; a[cx][cy]=0; for(int i=0;i<4;i++) { tx=cx+dx[i]; ty=cy+dy[i]; if(tx==hb&&ty==lb) { ans=dp[cx][cy]+1; return ; } if(a[tx][ty]) { que[++t][0]=tx; que[t][1]=ty; dp[tx][ty]=dp[cx][cy]+1; } } } } int main(){ int n,m; string ch; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>ch; for(int j=1;j<=m;j++) { if(ch[j-1]=='.')a[i][j]=1; if(ch[j-1]=='S')ha=i,la=j; if(ch[j-1]=='T')hb=i,lb=j; } } dp[ha][la]=0; bfs(); cout<<ans; return 0; }
究其错误原因，我第一个想到的是数组开小了（以前也遇到数组开小了会出现这样的运行错误），然后我把数组中102改为1000，好像是多了一个点正确。但又一想，不对啊，n和m不超过100，最大队列也就100*100啊，所以，这不是根本。突然我想到了在做“抓住那头牛”时遇到的答案不正确的情况（当时进行了调试，找到了错误），让我明白错在哪。（抓住那头牛链接：一本通网站1253）我当时输入的测试数据是5 22，定义的搜索顺序是-1 +1 *2，当时写的也是一个跟这个差不多的广搜。也就是先设置搜索的基础数为5，然后可以依次搜到4 6 10，让5出队，4 6 10进队，以4为基础，4出队，3/8入队（+1可以搜到5，但5己被搜过，不入队），接着是6出队，7/12入队，10出队，9/11/20入队，3出队，2入队，这时队列里有元素（5 4 6 10 3 8 7 12 9 11 20 2）队头指针指向8，8出队，7/9会不会入队呢？按照我的这个思路，7/9不应该入队，但这两数确实再次入队了，因为程序置己被搜索标记的是a[cx][cy]=0,这一语句放在了从队列取出元素之后，7/9尚未取出，当然就没有放置己被搜索过标记，所以会再次入队，那这样就会循环搜索，导致结果错误。也就是说，放置“己被搜索”标记的时间错了，它的正确时间应该是入队之后马上进行，而不是取出之后。1253是这么改的，如果原因真是这个的话，那这处程序也就是调整下标记位置就可以了。好，程序调整a[cx][cy]=0到入队的位置（当然要做一点小改动，变为a[tx][ty]=0),然后运行，没问题，提交，10个点全过。放上调整后代码：
#include<bits/stdc++.h> using namespace std; int const mx=102; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int a[mx][mx],que[mx*mx][2],ans,dp[mx][mx],ha,la,hb,lb; void bfs() { int h=0,t=0,cx,cy,tx,ty; que[0][0]=ha,que[0][1]=la; while(h<=t) { cx=que[h][0],cy=que[h++][1]; //a[cx][cy]=0; //这是一个错误位置 for(int i=0;i<4;i++) { tx=cx+dx[i]; ty=cy+dy[i]; if(tx==hb&&ty==lb) { ans=dp[cx][cy]+1; return ; } if(a[tx][ty]) { que[++t][0]=tx; que[t][1]=ty; dp[tx][ty]=dp[cx][cy]+1; a[tx][ty]=0;//这才是它的正确位置 } } } } int main(){ int n,m; string ch; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>ch; for(int j=1;j<=m;j++) { if(ch[j-1]=='.')a[i][j]=1; if(ch[j-1]=='S')ha=i,la=j; if(ch[j-1]=='T')hb=i,lb=j; } } dp[ha][la]=0; bfs(); cout<<ans; return 0; }
借石室中学小文老师的话总结：广搜一大要点：进队一个标记一个。（在此特别明谢小文老师的诸多帮助）
编后语：在这一个程序没有判断是否出界，不是我忘记了，我是用的数组自动初始化为0，跟墙的效果一样，而且在设置地图值时下标从1开始，避免数组出界，最大值设为102（不是101），最大下标可以比最大允许值大1，这样上/下都不会出界。在另一个程序马的走法时，同样道理，数组上限应比最大允许值大4（上/下边界各2，最小下标从2开始）