前言
最近板子题刷多了……
题意
一个 \(8\times 8\) 的棋盘，问马从起点到终点的最短步数为多少。
\(\sf Solution\)
要求最短路径嘛，显然 bfs 更优。
读入
这个读入处理有点麻烦……
我们可以把表示行的字符转化为数字，即 ch-‘a‘+1 。
搜索
将起点入队，每次获取队首元素并相应扩展，记录步数。
搜到的第一条路径就是最短路径，直接输出 step 。
\(\sf Code\)
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
struct node
{
int x,y,step;
} o;
queue<node>q;
int dx[8]={-1,1,-1,1,-2,2,-2,2},
dy[8]={-2,2,2,-2,-1,1,1,-1};//马的八个方向
bool vis[10][10];//标记数组
int sx,sy,ex,ey,xx,yy;
char ch;
string qx,qy;
int main()
{
while(cin>>qx&&qx[0]!=EOF)
{
cin>>qy;
sx=qx[0]-‘a‘+1,sy=qx[1]-‘0‘;
ex=qy[0]-‘a‘+1,ey=qy[1]-‘0‘;//读入
memset(vis,false,sizeof(vis));//初始化
vis[sx][sy]=true;
q.push((node){sx,sy,0});
while(!q.empty())
{
o=q.front(),q.pop();
if(o.x==ex&&o.y==ey)//找到路径
{
cout<<"To get from "<<qx<<" to "<<qy<<" takes "<<o.step<<" knight moves.\n";
break;
}
for(int i=0;i<8;++i)//扩展
{
xx=o.x+dx[i],yy=o.y+dy[i];
if(xx<=0||yy<=0||xx>8||yy>8)
continue;
if(vis[xx][yy])
continue;//不符合要求的情况都排除
vis[xx][yy]=true,q.push((node){xx,yy,o.step+1});
}
}
while(!q.empty())
q.pop();//别忘记清空队列
}
return 0;
}