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