#include <stdio.h>
#include <math.h>
#include <deque>
#include <algorithm>
typedef char byte;
bool visite[2][16800000];
struct Point
{
byte x, y;
Point(){}
Point( byte a, byte b ): x(a), y(b) {}
};
bool operator< ( Point a, Point b )
{
if( a.x== b.x ) return a.y< b.y;
return a.x< b.x;
}
std::deque<int> Q[2];
Point bpos[4], epos[4];
int getstate( Point t[4] )
{
int r= 0;
for( int i= 0; i< 4; ++i )
{
r= r* 8+ (int)( t[i].x- 1 );
r= r* 8+ (int)( t[i].y- 1 );
}
return r;
}
void recover( Point t[4], int value )
{
for( int i= 3; i>= 0; i-- )
{
t[i].y= value% 8+ 1;
value/= 8;
t[i].x= value% 8+ 1;
value/= 8;
}
}
bool isok( int x, int y )
{
return x>= 1 && x<= 8 && y>= 1 && y<= 8;
}
int xx[4]= { 0, 0, 1, -1 };
int yy[4]= { 1,-1, 0, 0 };
bool bfs()
{
Q[0].push_back( getstate(bpos) );
visite[0][ getstate(bpos) ]= true;
Q[1].push_back( getstate(epos) );
visite[1][ getstate(epos) ]= true;
int s;
int steps= -1;
while( !Q[0].empty() || !Q[1].empty() )
{
if( Q[0].size()> Q[1].size() ) s= 1;
else s= 0;
if( Q[s].size()== 0 ) s= 1- s;
int size= Q[s].size(); steps++;
if( steps> 8 ) break;
while( size-- )
{
int state= Q[s].front(); Q[s].pop_front();
if( visite[1-s][state] ) return true;
bool map[10][10]= { false };
Point temp[4];
recover( temp, state );
for( int i= 0; i< 4; ++i )
map[ temp[i].x ][ temp[i].y ]= true;
Point deal[4];
for( int i= 0; i< 4; ++i )
{
byte x= temp[i].x, y= temp[i].y;
for( int j= 0; j< 4; ++j )
{
for( int k= 0; k< 4; ++k )
deal[k].x= temp[k].x, deal[k].y= temp[k].y;
int tx= x+ xx[j], ty= y+ yy[j];
if( isok(tx,ty) )
{
if( !map[tx][ty] )
{
deal[i]= Point( tx, ty );
std::sort( deal, deal+ 4 );
if( !visite[s][ getstate(deal) ] )
{
Q[s].push_back( getstate(deal) );
visite[s][getstate(deal)]= true;
}
}
else
{
int ttx= tx+ xx[j], tty= ty+ yy[j];
if( isok( ttx, tty ) && !map[ttx][tty] )
{
deal[i]= Point( ttx, tty );
std::sort( deal,deal+ 4 );
if( !visite[s][ getstate(deal) ] )
{
Q[s].push_back( getstate(deal) );
visite[s][getstate(deal)]= true;
}
}
}
}
}
}
}
} // while
return false;
}
int main()
{
int d;
while( scanf("%d",&d)!= EOF )
{
bpos[0].x= d;
for( int i= 1; i< 8; ++i )
{
scanf("%d",&d);
if( i& 1 ) bpos[i/2].y= d;
else bpos[i/2].x= d;
}
for( int i= 0; i< 8; ++i )
{
scanf("%d",&d);
if( i&1 ) epos[i/2].y= d;
else epos[i/2].x= d;
}
std::sort( bpos, bpos+ 4 );
std::sort( epos, epos+ 4 );
Q[0].clear(), Q[1].clear();
memset( visite, false, sizeof(visite) );
if( bfs() ) puts("YES");
else puts("NO");
}
return 0;
}
posted on 2009-01-04 15:21
Darren 阅读(428)
评论(0) 编辑 收藏 引用