【POJ1077】Eight

2015.08.02 14:24 Sun | 25次阅读 | 旧日oi | 固定链接 | 源码

题目大意:8数码问题。
题解
这次用A*和IDA*分别写了一遍。
先是A*的,对每一个状态用阶乘进位制的哈希办法搞一下,估价函数用除x之外的每个点到对应位置的曼哈顿距离之和。

我的程序

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 400005
struct node
{
    int num[9],p;
}st,tmp;
char s[2];
int f[N],d[N],move[N],fa[N];
bool vis[N];
struct cmp
{
    bool operator () (int a,int b)
    {
        if(f[a]==f[b]) return d[a]<d[b];
        return f[a]>f[b];
    }
};
priority_queue<int,vector<int>,cmp> q;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int pla[9][2]={{0,0},{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1}};
int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};
int hash(node &a)
{
    int ret=0;
    for(int i=0;i<9;i++)
    {
        int k=0;
        for(int j=i+1;j<9;j++) 
        k+=(a.num[j]<a.num[i]);
        ret+=fac[a.num[i]-1]*k;
    }
    return ret;
}
int cnt[10];
void get_node(int x,node &a)
{
    for(int i=2;i<=9;i++)
    {
        int k=x%i;x/=i;
        cnt[i]=k;
        a.num[i-1]=0;
    }
    a.num[0]=0;
    for(int i=9;i>1;i--)
    {
        int t=0;
        for(int j=8;j>=0;j--)
        {
            if(a.num[j]) continue;
            if(t==cnt[i]) 
            {
                a.num[j]=i;
                break;
            }
            t++;
        }
    }
    for(int i=0;i<9;i++) if(a.num[i]==0) a.num[i]=1;
    a.p=9-cnt[9]-1;
}
int h(node &a)
{
    int ret=0,k;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    if((k=a.num[i*3+j])!=9) 
        ret+=abs(i-pla[k][0])+abs(j-pla[k][1]);
    return ret;
}
void A_star()
{
    int u=hash(st),v,x,y,tx,ty;
    f[u]=h(st);fa[u]=-1;
    q.push(u);
    while(!q.empty())
    {
        u=q.top();q.pop();
        if(u==0) return;
        get_node(u,tmp);
        x=tmp.p/3,y=tmp.p%3;
        for(int i=0;i<4;i++)
        {
            tx=x+dx[i],ty=y+dy[i];
            if(tx<0||tx>2||ty<0||ty>2) continue;
            swap(tmp.num[x*3+y],tmp.num[tx*3+ty]);
            v=hash(tmp);
            if(vis[v]&&d[u]+1<d[v])
            {
                move[v]=i;fa[v]=u;
                f[v]=f[v]-d[v]+d[u]+1;d[v]=d[u]+1;
                vis[v]=1;q.push(v);
            }
            else if(!vis[v])
            {
                move[v]=i;fa[v]=u;
                d[v]=d[u]+1;f[v]=d[v]+h(tmp);
                vis[v]=1;q.push(v);
            }
            swap(tmp.num[x*3+y],tmp.num[tx*3+ty]);
        }
        vis[u]=1;
    }
}
int ans[105];
void print()
{
    int x=0,cnt=0;
    while(fa[x]!=-1) 
    {
        ans[++cnt]=move[x];
        x=fa[x];
    }
    for(int i=cnt;i;i--)
    {
        if(ans[i]==0) printf("u");
        if(ans[i]==1) printf("r");
        if(ans[i]==2) printf("d");
        if(ans[i]==3) printf("l");
    }
}
int main()
{
    for(int i=0;i<9;i++)
    {
        scanf("%s",s);
        if(s[0]=='x') st.p=i,st.num[i]=9;
        else st.num[i]=s[0]-'0';
    }
    A_star();
    if(vis[0]) print();
    else cout<<"unsolvable";
}
IDA*
这次不用hash状态了,每次设定一个dfs最大深度,然后从初始状态搜,如果在深度范围内搜到解就结束搜索,否则记录下一次需要的最小深度。除了用估价函数剪枝,还有一个剪枝就是不要来回搜,往左完了又往右,往上完了又往下。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int dx[4]={-1,0,0,1};
int dy[4]={0,1,-1,0};
int pla[9][2]={{0,0},{0,0},{0,1},{0,2},{1,0},{1,1},{1,2},{2,0},{2,1}};
char s[2];
int num[3][3],stx,sty,bound,ans;
int path[105];
int h()
{
    int ret=0,k;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    if((k=num[i][j])!=9) 
        ret+=abs(i-pla[k][0])+abs(j-pla[k][1]);
    return ret;
}
int dfs(int x,int y,int d,int pre)
{
    int t=h();
    if(!t) 
    {
        ans=1;
        return d;
    }
    if(t+d>bound) return t+d;
    int nxt=0x3f3f3f3f;
    for(int tx,ty,i=0;i<4;i++)
    if(i+pre!=3)
    {
        path[d]=i;
        tx=x+dx[i];ty=y+dy[i];
        if(tx<0||tx>2||ty<0||ty>2) continue;
        swap(num[x][y],num[tx][ty]);
        int k=dfs(tx,ty,d+1,i);
        if(ans) return k;
        nxt=min(nxt,k);
        swap(num[x][y],num[tx][ty]);
    }
    return nxt;
}
void print()
{
    for(int i=0;i<bound;i++)
    {
        if(path[i]==0) printf("u");
        if(path[i]==1) printf("r");
        if(path[i]==3) printf("d");
        if(path[i]==2) printf("l");
    }
}
int main()
{
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
        scanf("%s",s);
        if(s[0]=='x') num[i][j]=9,stx=i,sty=j;
        else num[i][j]=s[0]-'0';
    }
    bound=19;
    while(!ans&&bound<=100) 
        bound=dfs(stx,sty,0,-1);
    if(ans) print();
    else cout<<"unsolvable";
}```