bfs,hash,康托展開（UESTC 485，Game）

一開始時間複雜度算錯了。。。當時想一共9！個狀态，1000組資料，那麼總運算量為3.62880e8，隻要資料稍微水一點，那不就過了嘛~~

然而我又搞錯了，不但沒有考慮編碼解碼的時間複雜度，更沒有考慮狀态轉移的時間複雜度。

當時覺得編碼解碼，狀态轉移都是常數嘛，直接無視不就好啦。

而且前面幾題暴力做，結果時間才一點點，是以以為這題也一樣。（好吧其實還是自己一直都沒算對時間複雜度）

事實上狀态轉移是一個O（10），編碼解碼主要是為了記錄，記錄有多種方法，不一定要編碼解碼，但是哪怕最優方法也都要O（10）。

兩個常數乘起來就是O（100），鐵定要超了。以後不能輕視那些常數的小循環啊。。。

正解就不在這裡說了，看别人部落格吧。

這裡隻講時間複雜度的優化。

狀态轉移是沒法優化了，但是記錄可以優化。

主要就是三種方法嘛，一是map，二是編碼解碼，三是hash。

我們從最差到最好依次講起。

首先是最差的map，友善确實是友善，但是不但常數大，而且還帶logn，插入大概相當于O（100）。

然後是編碼解碼，用康托展開編碼解碼可以得到一個完美哈希函數。

關于康托展開：http://blog.csdn.net/dacc123/article/details/50952079

但是編碼和解碼需要兩重循環，插入大概相當于O（50）。

我覺得除非要用到雙射的性質，這個方法不算太好。

最後是hash，O（1）插入。

是以還是hash最好。

我的方法是把狀态儲存成一個int類型，是以得到子狀态至少也要O（10）。

如果正常儲存狀态，複制也要O（10）。

是以前面才說最優也要O（10），哪怕用hash。

代碼

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;


//Hash
const int Hashsize = 1000007;
const int maxstate = 362880;
struct Node
{
    int s,d,next;
}node[maxstate];
int head[Hashsize],tot;
void init()
{
    tot=0;
    memset(head,-1,sizeof(head));
}
inline int Hash(int s){return s%Hashsize;}
bool try_to_insert(int s,int d)
{
    int h = Hash(s);
    for(int i=head[h];~i;i=node[i].next) if(node[i].s==s) return false;
    node[tot].s=s;
    node[tot].d=d;
    node[tot].next=head[h];
    head[h]=tot++;
    return true;
}
int getd(int s)
{
    int h = Hash(s);
    for(int i=head[h];~i;i=node[i].next) if(node[i].s==s) return node[i].d;
    return inf;
}


int Read()
{
    int ret=0;
    char str[2];
    for(int i=0;i<9;i++)
    {
        scanf("%s",str);
        ret*=10;
        if(isdigit(str[0])) ret+=str[0]-'0';
    }
    return ret;
}

int bit[9];

void res(int s)
{
    for(int i=8;i>=0;i--)
    {
        bit[i]=s%10;
        s/=10;
    }
}

int com()
{
    int ret=0;
    for(int i=0;i<9;i++)
    {
        ret*=10;
        ret+=bit[i];
    }
    return ret;
}

int next(int u,int x)
{
    res(u);
    if(x==1)
    {
        swap(bit[0],bit[6]);
        swap(bit[0],bit[3]);
    }
    else if(x==2)
    {
        swap(bit[1],bit[7]);
        swap(bit[1],bit[4]);
    }
    else if(x==3)
    {
        swap(bit[2],bit[8]);
        swap(bit[2],bit[5]);
    }
    else if(x==4)
    {
        swap(bit[6],bit[0]);
        swap(bit[6],bit[3]);
    }
    else if(x==5)
    {
        swap(bit[7],bit[1]);
        swap(bit[7],bit[4]);
    }
    else if(x==6)
    {
        swap(bit[8],bit[2]);
        swap(bit[8],bit[5]);
    }
    else if(x==7)
    {
        swap(bit[0],bit[2]);
        swap(bit[0],bit[1]);
    }
    else if(x==8)
    {
        swap(bit[3],bit[5]);
        swap(bit[3],bit[4]);
    }
    else if(x==9)
    {
        swap(bit[6],bit[8]);
        swap(bit[6],bit[7]);
    }
    else if(x==10)
    {
        swap(bit[2],bit[0]);
        swap(bit[2],bit[1]);
    }
    else if(x==11)
    {
        swap(bit[5],bit[3]);
        swap(bit[5],bit[4]);
    }
    else
    {
        swap(bit[8],bit[6]);
        swap(bit[8],bit[7]);
    }
    return com();
}

void pre()
{
    init();
    queue<int>q;
    q.push(123456789);
    try_to_insert(123456789,0);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=1;i<=12;i++)
        {
            int v = next(u,i);
            if(try_to_insert(v,getd(u)+1)) q.push(v);
        }
    }
}

int MAP[10];
int ans;
int vis[10];

void dfs(int cur,int num)
{
    if(cur==9)
    {
        ans=min(ans,getd(num));
        return;
    }
    else if(bit[cur]) dfs(cur+1,num*10+MAP[bit[cur]]);
    else for(int i=1;i<=9;i++) if(!vis[i])
    {
        vis[i]=1;
        dfs(cur+1,num*10+MAP[i]);
        vis[i]=0;
    }
}

void solve()
{
    int s,t;
    s=Read();
    t=Read();
    res(s);
    for(int i=0;i<9;i++) MAP[bit[i]]=i+1;
    res(t);
    memset(vis,0,sizeof(vis));
    for(int i=0;i<9;i++) if(bit[i]) vis[bit[i]]=1;
    ans = inf;
    dfs(0,0);
    if(ans==inf) puts("No Solution!");
    else printf("%d\n",ans);
}

int main()
{
    pre();
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        printf("Case #%d: ",t);
        solve();
    }
    return 0;
}