http://acm.pku.edu.cn/JudgeOnline/problem?id=1198
Код:
#include<iostream> #include<queue> #include<ext/hash_map> typedef unsigned long long u64_t; using namespace std; using namespace __gnu_cxx; struct hash_u64_t{ int operator()(u64_t v) const { return (v>>32)|(v&0xffffffff); } }; hash_map<u64_t, int, hash_u64_t> tab; int pos[4] = {0, 1, 2, 3}; u64_t s = 0x0fll,d; const u64_t base = 0x01llu; int mark[8][8]; int direct[4][2] = { {-1, 0}, {1,0}, {0,-1}, {0,1} }; int readIn(){ int x,y; s = d = 0; for(int i=0;i<4;i++){ if(scanf("%d%d",&x,&y)<0) return 0; x -- , y --; s |= base<<(8*x+y); } for(int i=0;i<4;i++){ scanf("%d%d",&x,&y); x -- , y --; d |= base<<(8*x+y); } return 1; } int fun(){ static int tstcase = 0; tstcase++; queue<u64_t> q; int p; tab.clear(); tab[s] = 0; q.push(s); int i,j,x,y,nx,ny; u64_t next; while(!q.empty()){ s = q.front(); q.pop(); p = tab[s]; j = 0; for(i=0;i<64;i++){ if(0== (s&(base<<i)) ) mark[i/8][i%8] = 0; else { pos[j++] = i; mark[i/8][i%8] = 1; } } for(i=0;i<4;i++){ x = pos[i] / 8; y = pos[i] % 8; for(j=0;j<4;j++){ // 16 ????? nx = x + direct[j][0]; ny = y + direct[j][1]; if(nx >=8||nx<0||ny>=8||ny<0) continue; if(mark[nx][ny] == 0){ next= s; next^= base<<pos[i]; next |=base<<(nx*8+ny); if(d == next) return 1; else if(tab.find(next) == tab.end() && p < 7){ tab[next] = p + 1; q.push(next); } } else { nx += direct[j][0]; ny += direct[j][1]; if(nx >=8||nx<0||ny>=8||ny<0) continue; if(mark[nx][ny] == 0){ next = s; next ^= base<<pos[i]; next |=(base<<(nx*8+ny)); if(d == next) return 1; else if(tab.find(next) == tab.end() && p < 7){ tab[next] = p + 1; q.push(next); } } } } } } return 0; } int main(){ const char *ans[2] = {"NO","YES"}; while(readIn()) printf("%s\n",ans[fun()]); return 0; }