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 |
单向BFS 94MS,用了位压缩,哈哈哈,是我自己想出来的,不过翻转位的操作太渣了,将就着看吧//3位可以表示8个数,然后从第25位起表示X的位置。x的值用000表示 #include<cstdio> #include<cstring> const int MAXSIZE = 1e6; const int HASHSIZE = 1e6 + 3; const int mask = 1|2|4; int hashTable[HASHSIZE]; int front,rear,cur; void inline lookbit(int x){ for(unsigned i = 1<<31;i;i>>=1) printf("%d",i&x?1:0); printf("\n"); } struct A{ int state,p; char dir; }Q[MAXSIZE]; struct B{ int state,nx; }next[MAXSIZE]; inline int swap(int x, int dist){ int l=x>>27; int t=0; t|=(((x>>(8-(l+dist))*3))&mask)<<(8-l)*3; x&=~(mask<<(8-l-dist)*3); t|=x; t&=~0U>>5; return t|((l+dist)<<27); } void printAns(int c,int s){ if(Q[c].state != s){ printAns(Q[c].p,s); putchar(Q[c].dir); } } inline int getHashNum(int x){ return x % HASHSIZE; } bool trytoInsert(int x){ int i = getHashNum(x); int l = hashTable[i]; while(l != -1){ if(next[l].state == x) return false; l = next[l].nx; } next[cur].nx = hashTable[i]; next[cur].state = x; hashTable[i] = cur++; return true; } void bfs(int s,int t){ register int temp; Q[rear++].state = s; while(front < rear){ int x = Q[front++].state; if(x==t){ printAns(front-1,s); return; } int z = x>>27; if(z/3>0){ temp = swap(x, -3); if(trytoInsert(temp)){ Q[rear].state = temp; Q[rear].dir = 'u'; Q[rear++].p = front - 1; } } if(z/3<2){ temp = swap(x, 3); if(trytoInsert(temp)){ Q[rear].state = temp; Q[rear].dir = 'd'; Q[rear++].p = front - 1; } } if(z%3>0){ temp = swap(x, -1); if(trytoInsert(temp)){ Q[rear].state = temp; Q[rear].dir = 'l'; Q[rear++].p = front - 1; } } if(z%3<2){ temp = swap(x, 1); if(trytoInsert(temp)){ Q[rear].state = temp; Q[rear].dir = 'r'; Q[rear++].p = front - 1; } } } printf("unsolvable\n"); } int main(){ memset(hashTable,-1,sizeof(hashTable)); char str[2]; int s = 0, t = 0, j = 24; for(int i = 0; i < 9; i++, j -= 3){ scanf("%s",str); if(*str!='x'){ s|=*str-'1'<<j; }else{ s|=i<<27; } } j = 24; t|= 8<<27; for(int i = 0; i < 8; i++, j -= 3){ t|=i<<j; } bfs(s,t); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator