| ||||||||||
| 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