题目背景：
《爱与愁的故事第三弹·shopping》娱乐章。
调调口味来道水题。
题目描述：
爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？
输入格式：
第1行：两个整数x1，y1
第2行：两个整数x2，y2
输出格式：
第1行：黑马到1,1的步数
第2行：白马到1,1的步数
样例输入：
12 16
18 10
样例输出：
8
9
说明/提示：
100%数据：x1,y1,x2,y2<=20（切记，n可不是开到20就OK的，地图范围开小了会WA的！！！）
AC Code：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=101;//这是个坑点，N开小了就会WA bool book[N][N];//标记数组 int m,n,p,q,head,tail; //题目描述中说马不仅可以走日，也可以走田，所以一共有12个方向 int dx[]={-1,-2,-2,-2,-2,-1,1,2,2,2,2,1}; int dy[]={2,2,1,-1,-2,-2,-2,-2,-1,1,2,2}; struct node { int x,y,step; }que[N*N];//定义结构体模拟队列 bool judge(int x,int y) {//不越界，并且这个点没有访问过 if(x>=1&&x<=N&&y>=1&&y<=N&&book[x][y]==false) { return true; } return false; } void bfs(int a,int b) { head=tail=1;//初始化队头队尾 que[head].x=a;//起点入队，这次终点是(1,1) que[head].y=b; que[head].step=0;//步数初始化为0 book[a][b]=true;//标记该点已走过 tail++;//起点入队，队尾向后移动一格 while(head<tail) { for(int i=0;i<12;i++) {//12个方向搜索 int tx=que[head].x+dx[i]; int ty=que[head].y+dy[i]; if(judge(tx,ty)) {//合法判断 book[tx][ty]=true;//标记新入队的点 que[tail].x=tx;//新的点入队 que[tail].y=ty; que[tail].step=que[head].step+1;//步数更新+1 tail++;//相应的队尾向后移动一格 if(tx==1&&ty==1) {//走到终点 printf("%d\n",que[tail-1].step); return ; } } } head++;//队头向后移动一格，继续下一个点的搜索 } return ; } int main() { memset(book,false,sizeof(book));//第一次搜索前，标记数组清零 scanf("%d %d",&m,&n); bfs(m,n);//搜索黑马 memset(book,false,sizeof(book));//注意：第二次搜索前，标记数组一定要再次清零！！！ scanf("%d %d",&p,&q); bfs(p,q);//搜索白马 return 0; }
