POJ-1077 Eight(康托展开+BFS)

POJ-1077 康托展开+BFS

前置知识

康托展开：

https://blog.csdn.net/qq_38701476/article/details/81003290

code（注释详解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<cstring>
#include<set>
#include<stack>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<iostream>
#include<map>
using namespace std;
int fac[15]={1,1,2,6,24,120,720,5040,40320,362880};
string path;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//u,d,l,r
char index[5]="udlr";
int aim=46234;//{1234567890}的cantor展开
bool visit[900005];
struct node{
    int loc;//x的位置
    int s[10];//3*3的元素构成的棋盘
    string path;//路径
    int hashval;//当前状态对应的hash值
}chess;

int cantor(int s[])//康托展开
{
    int sum=0;
    for(int i=0;i<9;i++)
    {
        int cnt=0;
        for(int j=i+1;j<9;j++)
        {
            if(s[i]>s[j])
                cnt++;
        }
        sum+=cnt*fac[8-i];
    }
    return sum+1;
}

bool bfs()
{
    queue<node>q;
    node cur;//当前棋盘局势
    node next;//下一棋盘局势
    q.push(chess);
    visit[chess.hashval]=true;//将初始局面先标记为使用过
    while(!q.empty())
    {
        cur=q.front();//将node队列头的棋盘局势作为cur
        q.pop();//用过后pop掉这个节点
        if(cur.hashval==aim)//如果当前节点的hashval=aim目标局面的hash值
        {
            path=cur.path;//把记录的路径赋给path
            return true;//返回true，退出bfs函数
        }
        int x=cur.loc/3;//当前x的位置的纵坐标
        int y=cur.loc%3;//当前x的位置的横坐标
        for(int i=0;i<4;i++)//遍历四个方向
        {
            int tempX=x+dir[i][0];//x下一次移动到的位置的横纵坐标
            int tempY=y+dir[i][1];

            if(tempX<0||tempY<0||tempX>2||tempY>2)
                continue;
            next=cur;//先把当前节点赋给next，这是为了在cur局面上移动才是next，所以要先赋给next
            next.loc=3*tempX+tempY;//x下一次移动道德位置的横纵坐标
            //下面将实现x位置与和它相邻位置的转换
            //1.先把将要是x位置中的数放到以前是x的位置
            next.s[cur.loc]=next.s[next.loc];
            //2.即将是x的位置转换为x，赋值为0
            next.s[next.loc]=0;

            next.hashval=cantor(next.s);//将新的顺序康托展开作为hashval

            if(next.hashval==aim)
            {
                next.path=cur.path+index[i];//记录这次操作index[i]，并加入路径
                path=next.path;
                return true;
            }
            if(visit[next.hashval])
                continue;
            next.path=cur.path+index[i];
            visit[next.hashval]=true;
            q.push(next);
        }
    }
    return false;
}
int main()
{
    char ch[10];
    memset(visit,false,sizeof visit);//初始化棋盘全部未访问过
    for(int i=0;i<9;i++)
    {
        scanf("%s",ch);
        if(ch[0]=='x')//如果当前位置为x
        {
            chess.s[i]=0;//记录这个元素的值为0并记录位置
            chess.loc=i;//记录x在几号位置
        }
        else
        {
            chess.s[i]=ch[0]-'0';//记录非x的元素的值所在位置
        }
    }
    chess.hashval=cantor(chess.s);//将起始状态进行康托展开作为棋盘初始的hashval值
    bool flag=bfs();//对初始局面进行bfs
    if(flag)
        cout<<path<<endl;
    else
        cout<<"unsolvable"<<endl;
    return 0;
}