题意：有上一状态到下一状态
单向bfs
就是每次只改变一个点的一个方向！！！
( 参考。。。http://blog.csdn.net/cscj2010/article/details/7371482)
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 const int maxn = 8; 8 bool vis[ maxn ][ maxn ][ maxn ][ maxn ][ maxn ][ maxn ][ maxn ][ maxn ]; 9 bool mat[ maxn+1 ][ maxn+1 ]; 10 struct node{ 11 int x,y; 12 }a[ maxn ]; 13 struct node2{ 14 int x[4],y[4],t; 15 }p,pp; 16 void init(){ 17 memset( mat,false,sizeof( mat )); 18 } 19 const int dx[]={0,0,1,-1}; 20 const int dy[]={1,-1,0,0}; 21 22 bool ok( node2 p ){ 23 for( int i=0;i<4;i++ ){ 24 if( mat[ p.x[i] ][ p.y[i] ]==false ) 25 return false; 26 } 27 return true; 28 } 29 30 bool empty( node2 pp,int i ){ 31 for( int k=0;k<4;k++ ){ 32 if( i!=k ){ 33 if( pp.x[i]==pp.x[k]&&pp.y[i]==pp.y[k] ){ 34 return false; 35 } 36 } 37 } 38 return true; 39 } 40 41 int bfs(){ 42 for( int i=0;i<4;i++ ){ 43 p.x[i]=a[i].x; 44 p.y[i]=a[i].y; 45 // p.t=0; 46 } 47 p.t=0; 48 if( ok(p)==true ) 49 return p.t; 50 queue<node2>q; 51 q.push( p ); 52 memset( vis,false,sizeof( vis )); 53 vis[ p.x[0] ][ p.y[0] ][ p.x[1] ][ p.y[1] ][ p.x[2] ][ p.y[2] ][ p.x[3] ][ p.y[3] ]=true; 54 while( !q.empty() ){ 55 p=q.front(),q.pop(); 56 if( p.t>=8 ) 57 return -11; 58 if( ok(p)==true ) 59 return p.t; 60 for( int i=0;i<4;i++ ){ 61 for( int j=0;j<4;j++ ){//dir 62 pp=p; 63 pp.x[ i ]=p.x[ i ]+dx[ j ]; 64 pp.y[ i ]=p.y[ i ]+dy[ j ]; 65 pp.t=p.t+1; 66 if( pp.x[0]<0||pp.x[0]>=8||pp.y[0]<0||pp.y[0]>=8||pp.x[1]<0||pp.x[1]>=8||pp.y[1]<0||pp.y[1]>=8 ) 67 continue; 68 if( pp.x[2]<0||pp.x[2]>=8||pp.y[2]<0||pp.y[2]>=8||pp.x[3]<0||pp.x[3]>=8||pp.y[3]<0||pp.y[3]>=8 ) 69 continue; 70 if( vis[ pp.x[0] ][ pp.y[0] ][ pp.x[1] ][ pp.y[1] ][ pp.x[2] ][ pp.y[2] ][ pp.x[3] ][ pp.y[3] ]==true ) 71 continue; 72 if( empty( pp,i )==true ){ 73 vis[ pp.x[0] ][ pp.y[0] ][ pp.x[1] ][ pp.y[1] ][ pp.x[2] ][ pp.y[2] ][ pp.x[3] ][ pp.y[3] ]=true; 74 if( ok(pp)==true ) 75 return pp.t; 76 q.push( pp ); 77 } 78 else{ 79 pp.x[i]+=dx[j]; 80 pp.y[i]+=dy[j]; 81 if( pp.x[0]>=0&&pp.x[0]<8&&pp.y[0]>=0&&pp.y[0]<8&&pp.x[1]>=0&&pp.x[1]<8&&pp.y[1]>=0&&pp.y[1]<8&&pp.x[2]>=0&&pp.x[2]<8&&pp.y[2]>=0&&pp.y[2]<8&&pp.x[3]>=0&&pp.x[3]<8&&pp.y[3]>=0&&pp.y[3]<8 ){ 82 if( empty( pp,i )==true&&vis[ pp.x[0] ][ pp.y[0] ][ pp.x[1] ][ pp.y[1] ][ pp.x[2] ][ pp.y[2] ][ pp.x[3] ][ pp.y[3] ]==false ){ 83 vis[ pp.x[0] ][ pp.y[0] ][ pp.x[1] ][ pp.y[1] ][ pp.x[2] ][ pp.y[2] ][ pp.x[3] ][ pp.y[3] ]=true; 84 if( ok(pp)==true ) 85 return pp.t; 86 q.push( pp ); 87 } 88 } 89 } 90 } 91 } 92 } 93 return -11; 94 } 95 96 int main(){ 97 while( scanf("%d%d",&a[0].x,&a[0].y)==2 ){ 98 a[0].x--,a[0].y--; 99 for( int i=1;i<4;i++ ){ 100 scanf("%d%d",&a[i].x,&a[i].y); 101 a[i].x--,a[i].y--; 102 } 103 init(); 104 int x,y; 105 for( int i=0;i<4;i++ ){ 106 scanf("%d%d",&x,&y); 107 x--,y--; 108 mat[x][y]=true; 109 } 110 int flag=bfs( ); 111 if( flag!=-11 ) 112 printf("YES\n"); 113 else 114 printf("NO\n"); 115 } 116 return 0; 117 }