题目描述：
在一个 8 * 8 的棋盘上，有四个棋子，每颗棋子可在上，下，左，右，四个方向进行四种操作,四种操作是一
下的某一种：
1. 若相邻格有棋子，则可像跳棋一样，跳过去，到达对称的一格。
2.若相邻格为空，则可直接移过去。
问能否从一种状态在8步之内变成另一种状态？
题目分析：
明显的一道搜索题，但是应该选取怎样的策略去搜索呢？
估计一下普通广度优先搜索的复杂度：有4颗棋子，每个棋子最多有4种变换方式，所以一个棋盘可以对应16种状态，走8步的话，就有16^8 = 2^32的计算量，这几乎不能完成任务。
考虑一下，这个题目的特别之处：给定两种状态，判断是否可达。操作的特别之处：操作具有可逆性，也就是说，从A到B状态，B到A依然是可行的。
所以，可虑一下双向广搜，先判断复杂度：两个状态各进行4步操作，计算量为16^4=2^16，时空复杂度都可以满足。考虑到这里不要求最小步数，我们可以先把两种状态各走四步的可达状态先用广搜算出存表，然后直接查表比较即可。
经过改进，湖南师范大学OJ的数据比POJ数据强很多。
http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=10708&courseid=38参考程序
#include<iostream>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
typedef __int64 i64;
const i64 one = (i64)1;
const int maxn = 1<<17 ;
int dx[4] = 
{ 1 , 0 ,-1 , 0 } ;
int dy[4] = { 0 , 1 , 0 , -1 };
struct node
{
i64 bd;
int pos[4];
};
node st , ed ;
i64 stq[maxn] ,edq[maxn] , sz ,ez ;
set<i64> win ;
set<i64>:: iterator it ;
bool IsOut( int cx,int cy)
{
return cx <0 || cy < 0 || cx >=8 || cy >=8 ;
}
bool IsOn( i64 bd ,int cx, int cy)
{
return bd & ( one<<(cx * 8 + cy) ) ;
}
void clr( i64 &bd ,int i)
{
if( ! IsOn( bd , i/8 , i%8) ) return ;
bd -= one<<i;
}
void put( i64 &bd, int i )
{
if(IsOn(bd ,i/8 ,i%8) ) return ;
bd += one <<i ;
}
bool next(node cur, int i,int j , node &son)
{
int t , tx , ty , nx , ny , cx , cy ;
i64 bd = cur.bd;
t = cur.pos[i] , tx = t / 8 , ty = t % 8 ;
nx = tx + dx[j] , ny = ty + dy[j] ;
if( IsOut(nx, ny) ) return false;
if( IsOn (bd , nx, ny) )
{
cx = 2*nx - tx, cy = 2*ny - ty;
if( IsOut(cx , cy) || IsOn(bd , cx , cy) ) return false;
clr(cur.bd, tx*8 + ty);
put(cur.bd, cx*8 + cy);
cur.pos[i] = cx * 8 + cy;
son = cur;
return true;
}
clr(cur.bd , tx * 8 + ty); put(cur.bd , nx * 8 + ny);
cur.pos[i] = nx * 8 + ny ;
son = cur;
return true;
}
void deal(node bgn )
{
int i , j , dep = 0 ;
node cur , son , tail;
queue<node> q;
tail.bd = -1 ;
win.clear(); win.insert(bgn.bd);
q.push(tail); q.push(bgn);
while(!q.empty())
{
cur = q.front(); q.pop();
if( cur.bd == -1 )
{
if(q.empty()) return ;
q.push(tail); cur = q.front() ; q.pop();
if( ++ dep > 4 ) return ;
}
for(i = 0 ; i < 4 ;++i)
for( j = 0 ;j < 4 ;++j )
if ( next( cur , i , j , son ) )
if( win.find(son.bd) ==win.end() )
{
q.push(son);
win.insert(son.bd);
}
}
}
int bbs(i64 x)
{
int l , r ,mid;
l = 0 , r = ez - 1 ;
while(l <= r)
{
mid = ( l + r) / 2 ;
if(edq[ mid ] == x) return mid ;
else if ( x < edq[mid] ) r = mid - 1;
else l = mid + 1;
}
return -1;
}
bool can()
{
int i , x[4],y[4] ,check ;
if(scanf("%d%d%d%d%d%d%d%d",&x[0],&y[0],&x[1],&y[1],&x[2],&y[2],&x[3],&y[3]) == EOF )
return false;
st.bd = 0 ;
for(i = 0 ; i<4 ; ++i)
{
-- x[i] , -- y[i] ;
put(st.bd , x[i] * 8 + y[i]);
st.pos[i] = x[i] * 8 + y[i];
}
ed.bd = 0 ;
for(i = 0 ; i<4 ; ++i)
{
scanf("%d%d",&x[i],&y[i]);
-- x[i] , -- y[i];
put(ed.bd , x[i] * 8 + y[i]);
ed.pos[i] = x[i] * 8 + y[i] ;
}
sz = ez = 0 ;
deal(st);
for(it = win.begin() ; it!=win.end(); it ++ )
stq[sz ++ ] = *it;
deal(ed);
for(it = win.begin() ; it!=win.end(); it++)
edq[ez ++ ] = *it ;
sort(edq , edq + ez);
check = 0 ;
for(i = 0 ; i < sz && !check ; ++i)
if( bbs(stq[i]) !=-1 )
check = 1;
if(check)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return true;
}
int main()
{
while(can());
return 0;
}