洛谷 P1379 八数码难题_洛谷 八数码

传送至原题

题目大意：

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

输入

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

输出

表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入样例

283104765
1

输出样例

4
1

这个题大佬们都是用什么康托展开，什么hash。。。
作为一个蒟蒻，我就写了个bool，暴力判断重。
可是九位的数组会爆啊，那我们就要想一个问题，一个数码是九位数，如果前面八位没有重复，那最后一位也不会重复，所以我们就可以开一个八位的数组来判重。

接下来讲讲主要思路：先找到0的位置，再枚举四个方向，交换值时打一个表就很好解决了还有要注意的是：当0在最左最右边时，它无法继续往左走或往右走。同样，在最上和最下面时也是这样的。

最后讲讲怎么交换位置：如样例中的283104765，要把它变成283164705，即交换0和6，怎么变呢？我们发现，0前面的数都没有变。这样，我们就可以把前面边的数提取出来，即把2831提取出来，再把6放在2831后面，再接上4765，就成了283164765。但是后面还是有个6，怎么办呢？减掉一个60不就行了！？那么把这段话用计算机语言表示除了就是

（283104765/10000+6）*10000+283103765%10000（+4786）-6*10
1

下面贴上代码：

#include <queue>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct node 
{
    int p;
    int i;
    int s;
};
int n,e=123804765;
int a[4]={1,3,-1,-3};
queue<node> q;
bool h[90000000];
int Count(int nows,int nowp,int nextp)//交换
{
    int b[9]={100000000,10000000,1000000,100000,10000,1000,100,10,1}
    int c,s;
    c=nows/b[nextp]%10;
    s=(nows/b[nowp]+c)*b[nowp]+nows%b[nowp]-c*b[nextp];
    return s;
}
int Bfs(node f)
{
    memset(h,false,sizeof(h));
    h[f.s/10]=true;
    q.push(f);
    while (!q.empty())
    {
        node now=q.front();
        q.pop();
        if (now.s==e) return now.i;//到达目标输出并结束
        for (int k=0;k<4;k++)
        {
            node next=now;
            next.p=now.p+a[k];
            if (now.p/3==2&&a[k]==3) continue;
            if (now.p/3==0&&a[k]==-3) continue;
            if (now.p%3==2&&a[k]==1) continue;
            if (now.p%3==0&&a[k]==-1) continue;
            next.s=Count(now.s,now.p,next.p);
            if (h[next.s/10]==false)
            {
                h[next.s/10]=true;
                next.i++;
                q.push(next);
            }
        }
    }
}
int main()
{
    node f;
    string s;
    cin>>s;
    for (int i=0;i<=s.size()-1;i++)
    {
        n=n*10+s[i]-'0';
        if (s[i]=='0') f.p=i;
    }
    f.s=n;
    f.i=0;
    cout<<Bfs(f)<<endl;
    return 0;
}
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

码字不易，看得懂的的请点赞