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 |
为什么本机<1s,提交T炸了???#include<cstdio> #include<string> #include<map> #include<queue> using namespace std; const int flg[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; int a[10],T; map<int,bool> hsh; map<int,int> las; struct dyt{int x,num;}; queue<dyt> Q; int get(int num,int x,int y){ int ret=0; for (int i=9;i>=1;i--) a[i]=num%10,num/=10; for (int i=1;i<=9;i++) if (i==x) ret=ret*10+a[y]; else if (i==y) ret=ret*10+a[x]; else ret=ret*10+a[i]; return ret; } void dfs(int x){ int num=las[x]; if (num==0) return; dfs(num); int p1,p2; for (int i=9;i>=1;i--) { if (x%10==0) p1=i; if (num%10==0) p2=i; x/=10,num/=10; } int x1=(p1-1)/3+1,y1=(p1-1)%3+1,x2=(p2-1)/3+1,y2=(p2-1)%3+1; if (x1-x2==1) printf("d"); else if (x1-x2==-1) printf("u"); else if (y1-y2==1) printf("r"); else if (y1-y2==-1) printf("l"); } int main(){ dyt u,v; freopen("b.in","r",stdin); for (int i=1;i<=9;i++){ char ch=getchar(); while ((ch<'0'||ch>'9')&&ch!='x') ch=getchar(); if (ch=='x') ch='0'; u.num=u.num*10+ch-48; if (ch=='0') u.x=i; } hsh[u.num]=1; Q.push(u); while (!Q.empty()){ T++; if (T>=300000) break; u=Q.front(); Q.pop(); if (u.num==123456780) break; int x=(u.x-1)/3+1,y=(u.x-1)%3+1; for (int i=0;i<4;i++){ int xx=x+flg[i][0],yy=y+flg[i][1]; if (xx<1||xx>3||yy<1||yy>3) continue; int num=get(u.num,u.x,(xx-1)*3+yy); if (hsh[num]) continue; hsh[num]=1; v.x=(xx-1)*3+yy,v.num=num,las[num]=u.num; Q.push(v); } } if (hsh[123456780]==0) {printf("unsolvable\n"); return 0;} dfs(123456780); printf("\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator