POJ 1077 Eight(BFS:输出路径)

POJ 1077 Eight(BFS:输出路径)

http://poj.org/problem?id=1077

题意:给你一个八数码3*3的网格,要你输出解的路径.

分析:参考刘汝佳入门经典P132.

首先对于每个网格状态,我们把它转化为一个9位的十进制数.然后用state[][9]二维数组来保存所有的我们已经发现的状态st,且用state[]来表示当前我们用的栈.

对于每个节点的判重,我们需要用到hash表来映射判重.

具体细节看代码,不过写完代码,发现了好多错误,写完后还是需要仔细的代码复查.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
const int max_state=1000003;  //错0,这里9!=362880,我看成了3W6,就写了100003了.导致存取越界
int dx[]={-1,1,0,0};//上,下,左,右
int dy[]={0,0,-1,1};
int goal[]={1,2,3,4,5,6,7,8,0};
struct Node
{
    int st[9];
    int d;//表示前一步的操作方向
    int pre;//前一个状态的下标
    Node(){}
}state[max_state];//state从1开始计数,因为0被看做不存在
struct HASHMAP
{
    int head[max_state];
    int next[max_state];
    void init(){memset(head,0,sizeof(head));}//初始化,0号状态代表不存在
    int hash(int *st)                        //这个st是一个st[9]
    {
        int v=0;
        for(int i=0;i<9;i++)
            v=v*10+st[i];
        return v%max_state;
    }
    bool try_insert(int st)                  //这个st是state的下标
    {
        int h=hash(state[st].st);
        int u=head[h];
        while(u)
        {
            if(memcmp(state[u].st,state[st].st,sizeof(state[u].st) )==0) return false;//状态已存在,插入失败
            u=next[u];
        }
        next[st]=head[h];
        head[h]=st;
        return true; //插入成功
    }
}hm;
int BFS()//返回目标状态的下标
{
    hm.init();
    int front=1,rear=2;//首状态已经读入state数组了
    while(front<rear)
    {
        Node node=state[front];
        int z,x,y;
        for(int i=0;i<9;i++) if(node.st[i]==0) {z=i;break;}//找到0的位置
        x=z/3 , y=z%3;                                     //x与y是0所在的行和列号
        for(int d=0;d<4;d++)
        {
            int nx=x+dx[d] ,ny=y+dy[d];
            if(nx>=0&&nx<3&&ny>=0&&ny<3)                    //错1,这里写成<=3了
            {
                int nz=nx*3+ny;//需要调换的位置
                state[rear] = node;
                state[rear].d=d;
                state[rear].st[z]=node.st[nz];
                state[rear].st[nz]=node.st[z];
                state[rear].pre=front;
                if(hm.try_insert(rear))
                {
                    rear++;
                    if(memcmp(goal,state[rear-1].st,sizeof(goal))==0) return rear-1; //错2,这里两个rear-1都写成了rear
                }
            }
        }
        front++;            //错3,这里忘了
    }
    return -1;
}
int main()
{
    char x;
    int i=0;
    while((x=getchar())!=EOF)
    {
        if(x=='x') state[1].st[i++]=0;
        else if(x>='1'&&x<='8') state[1].st[i++]=x-'0';
        if(i>=9) break;                                    //错4这里i忘了++
    }
    int ans=BFS();
    if(ans==-1) printf("unsolvable\n");
    stack<int> S;
    while(ans!=1)
    {
        S.push(state[ans].d);
        ans=state[ans].pre;
    }
    while(!S.empty())                 //错5,这里忘了!
    {
        int dir=S.top();S.pop();
        if(dir==0)putchar('u');
        else if(dir==1)putchar('d');
        else if(dir==2)putchar('l');
        else if(dir==3)putchar('r');
    }
}