| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
0ms 不虚#include<cstdio>
#include<cstring>
const int MAXN = 1<<16;
int dis[MAXN], q[MAXN];
int move[]={0xc800,0xe400,0x7200,0x3100,
0x8c80,0x4e40,0x2720,0x1310,
0x8c8,0x4e4,0x272,0x131,
0x8c,0x4e,0x27,0x13};
int Input() {
char in[6];
int ret=0;
for(int i=0; i<4; ++i)
{
scanf("%s", in);
for(int j=0; j<4; ++j)
{
ret <<= 1;
if(in[j]=='b') ret++;
}
}
return ret;
}
int BFS(int s) {
memset(dis, 0xff, sizeof(dis));
dis[s] = 0;
if(s==0||s==MAXN-1)
return 0;
int l, r;
l = r = 0;
q[r++] = s;
while(l!=r) {
int pos = q[l++];
//printf("step:%d\t%x\n", dis[pos], pos);
for(int i=0; i<16; ++i)
{
int np = pos^move[i];
if(np==0||np==MAXN-1) {
// printf("%d\n", np);
return dis[np]=dis[pos]+1;
}
if(dis[np]==-1) {
dis[np] = dis[pos]+1;
q[r++] = np;
if(r==MAXN) r = 0;
}
}
}
return -1;
}
int main() {
int pos = Input();
int step = BFS(pos);
if(step!=-1) printf("%d\n", step);
else puts("Impossible");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator