洛谷 P1379 八数码难题 解题报告

P1379 八数码难题

题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式

输入格式：

输入初始状态，一行九个数字，空格用0表示

输出格式：

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

---

虽然这个题没有用到，但还是提一下有解性判断

当棋盘长度是奇数时，有解等价于初始状态与目标状态的抽出来横着放的序列中逆序对个数的奇偶性相同

正常的解题思路：

用康托展开判重，用曼哈顿距离估价搜索

然而我最开始打的记搜wa的不行

最后终于想明白，有环记搜个锤子啊！！！

事实上状态量很少，直接广搜就可以

---

Code:

#include <cstdio>

#include <cstring>

const int N=1e6;

int s[10],fac[10],step[N],used[N],l,r;

int a[10]={0,2,3,4,9,1,5,8,7,6};

void add(int x){while(x<=9) ++s[x],x+=x&-x;}

int ask(int x){int su=0;while(x) su+=s[x],x-=x&-x;return su;}

struct node

{

    int a[10];

}q[N];

int kanton(node x)

{

    int ans=0;memset(s,0,sizeof(s));

    for(int i=1;i<=9;i++)

        ans+=fac[9-i]*(x.a[i]-1-ask(x.a[i])),add(x.a[i]);

    return ans;

}

void swap(int &x,int &y){int tmp=x;x=y,y=tmp;}

int main()

{

    fac[0]=1;node s;

    for(int i=1;i<=9;i++) fac[i]=fac[i-1]*i,s.a[i]=a[i];

    int to=kanton(s);

    char c[10];scanf("%s",c+1);

    for(int i=1;i<=9;i++) s.a[i]=c[i]-'0'+1;

    q[0]=s;step[0]=0;

    while(l<=r)

    {

        node now=q[l++];

        int id=kanton(now),pos;

        if(id==to) {printf("%d\n",step[l-1]);break;}

        if(used[id]) continue;used[id]=1;

        for(int i=1;i<=9;i++) if(now.a[i]==1) {pos=i;break;}

        if(pos%3!=1)

        {

            node t=now;

            swap(t.a[pos],t.a[pos-1]);

            q[++r]=t,step[r]=step[l-1]+1;

        }

        if(pos%3)

        {

            node t=now;

            swap(t.a[pos],t.a[pos+1]);

            q[++r]=t,step[r]=step[l-1]+1;

        }

        if(pos>3)

        {

            node t=now;

            swap(t.a[pos],t.a[pos-3]);

            q[++r]=t,step[r]=step[l-1]+1;

        }

        if(pos<7)

        {

            node t=now;

            swap(t.a[pos],t.a[pos+3]);

            q[++r]=t,step[r]=step[l-1]+1;

        }

    }

    return 0;

}

---

2018.8.30