马步距离（经典BFS） - 华师一附中OI组

///n*n的棋盘上马在x y处，跳到xx yy处至少需要几步？
#include <iostream>
#include <iomanip>
using namespace std;
const int mm=100010;/// 最多的状态数目
const int mn=13; ///棋盘最大12*12
struct horse
{
int x,y,f;
} a[mm],temp;
int m[mn][mn];///记录到达此点的最少步数，兼判断重复
int n,x,y,xx,yy;
int h,t;
int dx[]= {0,+1,+2,+2,+1,-1,-2,-2,-1};
int dy[]= {0,+2,+1,-1,-2,+2,+1,-1,-2};
bool can(int x,int y) ///xy点是否能到达
{
if (x<1 || x>n || y<1 || y>n) return 0;///越界
if (m[x][y]>-1) return 0;/// 已经经历
return 1;
}
void check()
{
int i,j;
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++) cout<<setw(2)<<m[i][j];
cout<<endl;
}
for (i=1; i<=40; i++) cout<<a[i].x<<' ';
cout<<endl;
for (i=1; i<=40; i++) cout<<a[i].y<<' ';
cout<<endl;
for (i=1; i<=40; i++) cout<<a[i].f<<' ';
cout<<endl;
}
void pp()
{
int i=1,j;
int p[50];///最多50步，表示路径
p[1]=j=h;
while (a[j].f!=0) p[++i]=j=a[j].f; ///非常精妙的写法
for (; i>=1; i--)cout<<a[p[i]].x<<' '<<a[p[i]].y<<"->";
cout<<xx<<' '<<yy;
}
int main()
{
n=8,x=1,y=1,xx=1,yy=2; ///初始
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) m[i][j]=-1;
m[1][1]=0;
bool b=1;
h=1,t=2;
a[h].x=1,a[h].y=1,a[h].f=0;
while (t<=mm-100 && h<t && b)
{
temp=a[h];
for (int r=1; r<=8; r++) /// 8个规则
{
int tx=temp.x+dx[r],ty=temp.y+dy[r];
cout<<tx<<' '<<ty<<endl;
if (tx==xx&& ty==yy) ///是目标节点
{
b=0;
break;
}
if (can(tx,ty)) ///符合条件加入队列
{
m[tx][ty]=m[temp.x][temp.y]+1; ///判断重复
a[t].x=tx,a[t].y=ty,a[t].f=h;
t++;
}
}
if(b==1)h++; ///未找到继续找，找到了就算了
}
check();
if (t>mm-100) cout<<"i cannot find!";
else if (h>t) cout<<"cannot find!";
else if (b==0) pp();
return 0;
}

复制代码