本文共 1551 字，大约阅读时间需要 5 分钟。
题意：8*8国际象棋棋盘，求马从起点到终点的最少步数。
编写时犯的错误：1、结构体内没构造。2、bfs函数里返回条件误写成起点。3、主函数里取行标时未注意书中的图。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int MAXN=10000+10;const int INF=0x7f7f7f7f;const double PI=acos(1.0);typedef long long ll;typedef unsigned long long llu;char s1[3];char s2[3];int vis[10][10];struct KK{ int x_,y_,bushu_;//x行标，y列标，bushu步数 KK(int x=0,int y=0,int bushu=0):x_(x),y_(y),bushu_(bushu){}//构造！构造！构造！};int stax[]={-2,-2,-1,-1,1,1,2,2};//马的八种移动方式int stay[]={-1,1,-2,2,-2,2,-1,1};//行x（上减下加），列y（左减右加）int bfs(int a,int b,int c,int d){ memset(vis,0,sizeof(vis));//！！！ queue q; q.push(KK(a,b,0));//将起点压入队列，此时步数为0 vis[a][b]=1;//标记！！！ while(!q.empty()) { KK tmp=q.front(); q.pop(); int tmpx=tmp.x_; int tmpy=tmp.y_; int tmpb=tmp.bushu_; if(tmpx==c&&tmpy==d)//若此时位置等于终点坐标，则返回步数 return tmpb; for(int i=0;i<8;i++)//从这一点遍历八个方向 { int tx=tmpx+stax[i]; int ty=tmpy+stay[i]; if(tx<0||tx>=8||ty<0||ty>=8)//越界 continue; if(!vis[tx][ty]) { q.push(KK(tx,ty,tmpb+1));//未被标记则压入，注意步数加1 vis[tx][ty]=1;//标记！！！ } } }}int main(){ while(scanf("%s%s",s1,s2)==2) { int a=8-(s1[1]-'0');//紫书上的图一到八行是8到1，这里取行标（从上到下----0~7） int b=s1[0]-'a';//列标 int c=8-(s2[1]-'0'); int d=s2[0]-'a'; int step=bfs(a,b,c,d); printf("To get from %s to %s takes %d knight moves.\n",s1,s2,step); } return 0;}
转载于:https://www.cnblogs.com/tyty-Somnuspoppy/p/5894129.html