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

开数组MLE,用map就T,我擦,我用hash 219ms过的,我擦擦擦,吐血了

Posted by WilliamACM at 2013-02-15 17:10:42 on Problem 1077
#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:
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