poj 1043

poj 1043

经典的八数码问题，这个问题最重要的是hash函数的使用，用来判重，因为是记录路径，所以用bfs最好了

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define M 362888
using namespace std;

int map[12];  bool vis[M];
struct NODE
{
    long long num,pre,dir;
}Q[M<<3];
int dt[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
long long step[M];
long long canto()
{
        int j, i, tmp;
        long long ans;
        for (ans = 1, i = 0; i < 9; i++)
        {
                for (tmp = map[i] - 1, j = 0; j < i; j++)
                        tmp -= (map[j] < map[i]);
                ans = ans + tmp * fact[8 - i];
        }
        return ans;
}
void antihash(long long num)
{
    int k=8;
    while(k!=-1)
    {
        map[k--]=num%10;
        num=num/10;
    }
}
long long hash()
{
    long long num=0;
    for(int i=0;i<=8;i++)
        num=num*10+map[i];
    return num;
}
long long bfs()
{
    int head=1,tail=2;
    long long sp=hash();
    Q[1].num=sp; Q[1].dir=-1; Q[1].pre=-1;
    long long val=canto(); vis[val]=true;
    while(head<tail)
    {
        int pos;
        NODE sta=Q[head];
        antihash(sta.num); val=canto();
        if(val==1) return(head);//stop
        for(int i=0;i<9;i++)//find pos
           if(map[i]==9) {pos=i;i=100;}
        int x=pos%3,y=pos/3;//pos
        for(int i=0;i<4;i++)
        {
            int nx=x,ny=y;
            nx+=dt[i][0];
            ny+=dt[i][1];
            if(ny>=0&&ny<3&&nx>=0&&nx<3)
            {
                int pos1=x+y*3;//last pos
                int pos2=nx+ny*3;//new pos
                swap(map[pos1],map[pos2]);
                val=canto();
                if(!vis[val])
                {
                    vis[val]=true;
                    NODE dick;
                    dick.num=hash(); dick.pre=head; dick.dir=i;
                    Q[tail++]=dick;
                }
                swap(map[pos1],map[pos2]);
            }
        }
        head++;
    }
    return -1;
}
void print(int hd)
{
    int wx=0;
    while(Q[hd].pre!=-1)
    {
        step[++wx]=Q[hd].dir;
        hd=Q[hd].pre;
    }
    for(int i=wx;i>=1;i--)
    {
        if(step[i]==0) printf("r");
        else if(step[i]==1) printf("d");
        else if(step[i]==2) printf("l");
        else if(step[i]==3) printf("u");
    }
}
void solve()
{
    int hd=bfs();
    if(hd==-1) printf("unsolvable");
    else print(hd);
}
int main()
{
    char a;
    for(int i=0;i<9;i++)
    {
        cin>>a;
        if(a=='x') map[i]=9;
        else map[i]=a-'0';
    }
    solve();
    //system("pause");
    return 0;
}

因为hash函数我并不是很理解，所以改成set，就TLE了，看来stl有时候还是谨慎使用呀

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <set>

#define M 362888
using namespace std;
int map[12];  bool vis[M];
struct NODE
{
    long long num,pre,dir;
}Q[M<<3];
set<int> st;
int dt[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//const int fact[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
long long step[M];
/*long long canto()
{
        int j, i, tmp;
        long long ans;
        for (ans = 1, i = 0; i < 9; i++)
        {
                for (tmp = map[i] - 1, j = 0; j < i; j++)
                        tmp -= (map[j] < map[i]);
                ans = ans + tmp * fact[8 - i];
        }
        return ans;
}*/
void antihash(long long num)
{
    int k=8;
    while(k!=-1)
    {
        map[k--]=num%10;
        num=num/10;
    }
}
long long hash()
{
    long long num=0;
    for(int i=0;i<=8;i++)
        num=num*10+map[i];
    return num;
}
long long bfs()
{
    int head=1,tail=2;
    st.clear();
    long long sp=hash();
    //cout<<sp<<endl;
    Q[1].num=sp; Q[1].dir=-1; Q[1].pre=-1;
    st.insert(sp);
    while(head<tail)
    {
        int pos;
        NODE sta=Q[head];
        if(sta.num==123456789) return head;
        antihash(sta.num);
        for(int i=0;i<9;i++)//find pos
           if(map[i]==9) {pos=i;i=100;}
        int x=pos%3,y=pos/3;//pos
        for(int i=0;i<4;i++)
        {
            int nx=x,ny=y;
            nx+=dt[i][0];
            ny+=dt[i][1];
            if(ny>=0&&ny<3&&nx>=0&&nx<3)
            {
                int pos1=x+y*3;//last pos
                int pos2=nx+ny*3;//new pos
                swap(map[pos1],map[pos2]);
                int val=hash();
                
                if(st.find(val)==st.end())
                {
                    st.insert(val);
                    NODE dick;
                    dick.num=val;
                    dick.pre=head;
                    dick.dir=i;
                    Q[tail++]=dick;
                }
                swap(map[pos1],map[pos2]);
            }
        }
        head++;
    }
    return -1;
}
void print(int hd)
{
    int wx=0;
    while(Q[hd].pre!=-1)
    {
        step[++wx]=Q[hd].dir;
        hd=Q[hd].pre;
    }
    for(int i=wx;i>=1;i--)
    {
        if(step[i]==0) printf("r");
        else if(step[i]==1) printf("d");
        else if(step[i]==2) printf("l");
        else if(step[i]==3) printf("u");
    }
}
void solve()
{
    int hd=bfs();
    if(hd==-1) printf("unsolvable");
    else print(hd);
}
int main()
{
    char a;
    for(int i=0;i<9;i++)
    {
        cin>>a;
        if(a=='x') map[i]=9;
        else map[i]=a-'0';
    }
    solve();
    //system("pause");
    return 0;
}