BFS，双向BFS的效率将会高些。 我写的是单向的，单向BFS想要不超时关键是，在内部循环，进行操作如果遇到结束就返回。用二维数组标记结束棋子的位置。方便检查是否结束。
下面是 AC代码：
[cpp] #include #include #include #include #include #include using namespace std; const int MAX =10; int a[10],b[10]; int n,flag; int dir[4][2]= {{1,0},{0,1},{-1,0},{0,-1}}; bool vis[8][8][8][8][8][8][8][8]; int hash[10][10]; struct node { int x[4]; int y[4]; int step; } s_pos; bool vail(int x,int y){ if(x>=0&&x<8&&y>=0&&y<8) return true; return false; } bool isempty(int x,int y,node now) { for(int i=0; i<4; i++) if(now.x[i]==x&&now.y[i]==y) return false; return true; } bool check(node now){ for(int i=0;i<4;i++){ if(!hash[now.x[i]][now.y[i]]) return false; } return true ; } bool visited(node next){ return vis[next.x[0]][next.y[0]][next.x[1]][next.y[1]] [next.x[2]][next.y[2]][next.x[3]][next.y[3]]; } void bfs() { s_pos.step=0; for(int i=1; i<=8; i++){ s_pos.x[i/2]=a[i]-1; i++; s_pos.y[i/2-1]=a[i]-1; } vis[s_pos.x[0]][s_pos.y[0]][s_pos.x[1]][s_pos.y[1]] [s_pos.x[2]][s_pos.y[2]][s_pos.x[3]][s_pos.y[3]]=1; queue q; q.push(s_pos); while(!q.empty()) { node now =q.front(); q.pop(); // for(int i=0;i<4;i++) cout< // cout< for( int i=0; i<4; i++) { for( int j=0; j<4; j++) { node next=now; next.x[i]+=dir[j][0], next.y[i]+=dir[j][1]; next.step=now.step+1; if(vail(next.x[i],next.y[i])&&next.step<=8) { if(!visited(next)){ if(isempty(next.x[i],next.y[i],now)){ //判断旁边是否有棋子，如果有就在跳一步 if(check(next)){ flag=1; return ;} vis[next.x[0]][next.y[0]][next.x[1]][next.y[1]] [next.x[2]][next.y[2]][next.x[3]][next.y[3]]=1; q.push(next); } else{ next.x[i]+=dir[j][0], next.y[i]+=dir[j][1]; if(vail(next.x[i],next.y[i])&&isempty(next.x[i],next.y[i],now)&&!visited(next)) { if(check(next)){ flag=1; return ;} vis[next.x[0]][next.y[0]][next.x[1]][next.y[1]] [next.x[2]][next.y[2]][next.x[3]][next.y[3]]=1; q.push(next); } } } } } } } } int main() { while(scanf("%d%d",&a[1],&a[2])!=EOF) { memset(vis,false,sizeof(vis)); memset(hash,0,sizeof(hash)); for(int i=3; i<=8; i++) scanf("%d",&a[i]); for(int i=1; i<=8; i++) scanf("%d",&b[i]); www.2cto.com for(int i=1;i<=8;i+=2){ hash[b[i]-1][b[i+1]-1]=1; } flag=0; bfs(); if(flag) printf("YES\n"); else printf("NO\n"); } return 0; }