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); 
 
                             } 
 
                         } 
                    } 
                } 
 
            } 
        } 
    } 
} 
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; 
}