zoj 1091 (bfs搜索)
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=91
?
结题报告：因该说10多天没有A题了，今天过了一道比较水的题目，也算是来纪念一下吧，最近在刷搜索的时候感觉bfs有些题目是比较难的，象蛇和梯子那道题整整卡了我一个星期但是现在仍然没有过，标记一下，有时间在回来看一下！
这道题注意两个地方，一个是下标的值，一个是vis数组标记！
?
#include<cstdio>#include<cstring>#include<queue>using namespace std;const int dir[8][2] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};int mp[9][9];int vis[9][9];struct node {int x,y;int step;};queue<node>Q;int ex,ey,sx,sy; int bfs(node p){node now,next;Q.push(p);while(!Q.empty()){now=Q.front();Q.pop();for(int i=0;i<8;i++){int xx = now.x+dir[i][0];int yy = now.y+dir[i][1];if(xx<1||xx>8||yy<1||yy>8) continue;if(xx == ex && yy == ey) {return now.step + 1;}if(!vis[xx][yy]){next.x=xx;next.y=yy;next.step = now.step+1;Q.push(next);}}}}int main( ){char str1[5],str2[5];while(scanf("%s%s",str1,str2)!=EOF){while(!Q.empty()) Q.pop();sx=str1[0]-'a'+1; sy=str1[1]-'0';ex=str2[0]-'a'+1; ey=str2[1]-'0';if(sx==ex&&sy==ey){printf("To get from %s to %s takes 0 knight moves.\n",str1,str2);continue;}memset(vis,0,sizeof(vis));vis[sx][sy]=1;node p;p.x = sx; p.y = sy; p.step = 0;printf("To get from %s to %s takes %d knight moves.\n",str1,str2,bfs(p));} }?