Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为什么本机<1s,提交T炸了???

Posted by _DYT at 2018-09-01 20:18:46 on Problem 1077
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator