1. 题目

传送门= ̄ω ̄=

2. 题解

就是个八数码问题,改了一下变换方式而已。同样是bfs+哈希记录状态。
哈希方法就是把数码的每一个格子里面的数字作为哈希值的每一位数字
哈希可以康托展开,这样就直接用数组哈希就行了。
我是直接用pb_ds哈希,直接水过。

代码:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize(2)
using namespace std;
using namespace __gnu_pbds;
typedef int st[3][3];
gp_hash_table<int,int> pre;
gp_hash_table<int,int> tot;
queue<int> que;
void stoi(int&tar,st a)
{
    tar=0;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)tar=tar*10+a[i][j];
}
void itos(st&tar,int a)
{
    memset(tar,0,sizeof(tar));
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)tar[i][j]=a%10,a/=10;
}
void midt(st&a){swap(a[1][1],a[1][2]),swap(a[1][0],a[1][1]);}
stack<int> sta;
void dfs(int a)
{
    if(!a)return;
    dfs(pre[a]);
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)sta.push(a%10),a/=10;
    for(int i=0;i<3;i++,putchar('\n'))
        for(int j=0;j<3;j++)printf("%d ",sta.top()),sta.pop();
    putchar('\n');
}
st beg;
int main()
{
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)scanf("%d",&beg[i][j]);
    int stb;
    stoi(stb,beg);
    que.push(stb),pre[stb]=0,tot[stb]=0;
    while(!que.empty())
    {
        int f=que.front();que.pop();
        st k;itos(k,f);
        midt(k);
        int p;stoi(p,k);
        if(!pre[p]&&p!=stb)que.push(p),pre[p]=f,tot[p]=tot[f]+1;
        midt(k),midt(k);
        int tem=k[0][0];
        k[0][0]=k[1][0],k[1][0]=k[2][0],k[2][0]=k[2][1],k[2][1]=k[2][2];
        k[2][2]=k[1][2],k[1][2]=k[0][2],k[0][2]=k[0][1],k[0][1]=tem;
        if(stoi(p,k),!pre[p]&&p!=stb)que.push(p),pre[p]=f,tot[p]=tot[f]+1;
    }
    if(!pre[12345678]&&12345678!=stb)puts("UNSOLVABLE"),exit(0);
    printf("%d\n",tot[12345678]),dfs(12345678);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

boshi · 2017年8月15日 2:02 下午

%%%55行

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *