hdu 1401
BFS，双向BFS的效率将会高些。
我写的是单向的，单向BFS想要不超时关键是，在内部循环，进行操作如果遇到结束就返回。用二维数组标记结束棋子的位置。方便检查是否结束。
下面是 AC代码：
[cpp]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
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<node > q;
q.push(s_pos);
while(!q.empty())
{
node now =q.front();
q.pop();
// for(int i=0;i<4;i++) cout<<now.x[i]<<" "<<now.y[i]<<" ";
// cout<<endl;
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);
}
}
}
}
}
}
}
}
