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 |
开数组MLE,用map就T,我擦,我用hash 219ms过的,我擦擦擦,吐血了#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <set> #include <queue> #include <map> #include <vector> using namespace std; int a[3][3],b[3][3],c[3][3]; const int N=42374117; const int H=1e7+7; int beg,vis[N]; int box[H],kk; struct node { int org,vis,next; }e[H]; int mx[5]={0,-1,0,1,0}; int my[5]={0,0,1,0,-1}; int map_num() { int ans=0,p=1; for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(i||j) { ans+=p*a[i][j]; p*=9; } return ans; } queue<int>q; int num_map(int now,int &x,int &y) { bool v[10]; memset(v,0,sizeof(v)); for(int i=1;i<9;i++) { if(now%9==8) { x=i/3; y=i%3; } v[now%9]=1; a[i/3][i%3]=now%9; now/=9; } for(int i=0;i<9;i++) if(!v[i]) { a[0][0]=i; if(i==8) { x=0; y=0; } } } bool in(int x,int y) { if(x<0||y<0||x>2||y>2) return 0; return 1; } int find(int num) { int af=num%H; for(int i=box[af];~i;i=e[i].next) if(e[i].org==num) return e[i].vis; return 0; } void add(int s,int num,int vis) { e[kk].org=num;e[kk].vis=vis,e[kk].next=box[s]; box[s]=kk++; } void hash_add(int num,int vis) { add(num%H,num,vis); } void pre() { for(int i=0;i<3;i++) for(int j=0;j<3;j++) a[i][j]=i*3+j; q.push(beg=map_num()); memset(box,-1,sizeof(box)); int cat=0; while(!q.empty()) { int now=q.front();q.pop(); int x,y; num_map(now,x,y); for(int i=1;i<=4;i++) { int nx=x+mx[i]; int ny=y+my[i]; if(!in(nx,ny)) continue; swap(a[x][y],a[nx][ny]); int nextNum=map_num(); swap(a[x][y],a[nx][ny]); if(find(nextNum)) continue; else { hash_add(nextNum,i); q.push(nextNum); ++cat; } } } } string s; void dfs(int x,int y,int level) { int key=find(map_num()); int nx=x-mx[key]; int ny=y-my[key]; if(map_num()==beg) return; char ch; switch(key) { case 1:ch='d';break; case 2:ch='l';break; case 3:ch='u';break; case 4:ch='r';break; } printf("%c",ch); swap(a[x][y],a[nx][ny]); dfs(nx,ny,level+1); } void init() { int x,y; for(int i=0;i<9;i++) { char s[2];scanf("%s",s); if(s[0]=='x') a[i/3][i%3]=8; else a[i/3][i%3]=s[0]-'1'; if(a[i/3][i%3]==8) { x=i/3; y=i%3; } } int nowNum=map_num(); if(find(nowNum)) { dfs(x,y,1); puts(""); }else puts("unsolvable"); } int main() { //freopen("in.txt","r",stdin); pre(); init(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator