Description
在一个8行9列的国际象棋棋盘上，有一名骑士在追杀对方的国王。该骑士每秒跨越一个2*3的区域，如下图所示。
而对方的国王慌忙落逃，他先沿着右下斜线方向一直跑，遇到边界以后会沿着光线反射方向继续跑（遇到死角则原路返回），他每秒只跑一格。
给出骑士和国王的初始位置，求最快在多少秒的时候骑士能追杀掉对方的国王。骑士和国王每一秒都必须要有行动，而不能原地等待。
Input
有多组测试数据。对于每组测试数据，输入只有一行：nx,ny,kx,ky，前2个表示骑士的初始坐标，后2个表示国王的初始坐标，以左上角的格子为(0,0),向右为x轴正方向，向下为y轴正方向。(0<=nx,kx<=8,0<=ny,ky<=7)
Output
对于每组测试数据，仅输出一个整数，即骑士追杀到国王的最快时刻。初始位置的时刻为0。追杀到的时刻是指骑士和国王处在同一格的时刻。
Sample Input
0 7 0 0
Sample Output
3
和正常的bfs不同，一个静点，一个动点，这个两个都是动点，求交汇处所需的最小步数，一个要注意移动的规则，还有就是重复走过的点，避免死循环。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <queue> #include <cstdlib> #include <iomanip> #include <cmath> #include <ctime> #include <map> #include <set> using namespace std; #define lowbit(x) (x&(-x)) #define max(x,y) (x>y?x:y) #define min(x,y) (x<y?x:y) #define MAX 100000000000000000 #define MOD 1000000007 #define pi acos(-1.0) #define ei exp(1) #define PI 3.141592653589793238462 #define ios() ios::sync_with_stdio(false) #define INF 1044266558 #define mem(a) (memset(a,0,sizeof(a))) typedef long long ll; int dirp[10][2]={{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1}}; int dirk[5][2]={{1,-1},{-1,-1},{-1,1},{1,1}}; int xp,yp,xk,yk; int turn[10][10][10][10][5]; struct Node { int px; int py; int kx; int ky; int step; }ans,pos; Node trans(Node a,int x) { int x1,x2,y1,y2,k; int nx1,nx2,ny1,ny2,nk; x1=a.px;y1=a.py;x2=a.kx;y2=a.ky;k=a.step; nx1=x1+dirp[x][0]; ny1=y1+dirp[x][1]; if(nx1<0 || ny1<0 || nx1>8 || ny1>7) {a.step=-1;return a;} if(x2==0 && y2==0 && k==1) nx2=1,ny2=1,nk=3; else if(x2==8 && y2==0 && k==0) nx2=7,ny2=1,nk=2; else if(x2==0 && y2==7 && k==2) nx2=1,ny2=6,nk=0; else if(x2==8 && y2==7 && k==3) nx2=7,ny2=6,nk=1; else if(x2==0 && (k==1 || k==2)) { nx2=1; if(k==1) ny2=y2-1,nk=0; else ny2=y2+1,nk=3; } else if(x2==8 && (k==0 || k==3)) { nx2=7; if(k==0) ny2=y2-1,nk=1; else ny2=y2+1,nk=2; } else if(y2==0 && (k==0 || k==1)) { ny2=1; if(k==0) nx2=x2+1,nk=3; else nx2=x2-1,nk=2; } else if(y2==7 && (k==2 || k==3)) { ny2=6; if(k==2) nx2=x2-1,nk=1; else nx2=x2+1,nk=0; } else nx2=x2+dirk[k][0],ny2=y2+dirk[k][1],nk=k; if(turn[nx1][ny1][nx2][ny2][nk]!=-1) {a.step=-1;return a;}//说明此情况已出现过无解，死循环。 turn[nx1][ny1][nx2][ny2][nk]=turn[x1][y1][x2][y2][k]+1; a.px=nx1;a.py=ny1;a.kx=nx2;a.ky=ny2;a.step=nk; return a; } void bfs(int x1,int y1,int x2,int y2) { queue<Node>q; int cnt=0; memset(turn,-1,sizeof(turn)); ans.px=x1;ans.py=y1;ans.kx=x2;ans.ky=y2;ans.step=3; turn[x1][y1][x2][y2][3]=0; q.push(ans); while(!q.empty()) { pos=q.front(); q.pop(); if(pos.px==pos.kx && pos.py==pos.ky) { cnt=turn[pos.px][pos.py][pos.kx][pos.ky][pos.step]; break; } for(int i=0;i<8;i++) { ans=trans(pos,i); if(ans.step>=0) q.push(ans); } } printf("%d ",cnt); } int main() { while(scanf("%d%d%d%d",&xp,&yp,&xk,&yk)!=EOF) { bfs(xp,yp,xk,yk); } return 0; }