洛谷P1379 八数码难题（提高+/省选-）广度优先BFS+康托展开；我做出了一道蓝题！使用广度优先BFS+康托展开

ゝ一世哀愁。 2022-11-09 11:21 155阅读 0赞

## P1379 八数码难题 ##

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

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

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

**输入输出样例**  
**输入**

283104765

**输出**

## 解题 ##

很多大佬都用双向BFS或者就是A\*算法，但是我都不会，所以我只能用康托展开了。

这里的BFS其实并不难写，重要的就是康托展开，此函数可以快速判重，能将 O ( n !   n ! ) O(n!\\ n!) O(n! n!)降低为 O ( n !   n 2 ) O(n!\\ n^2) O(n! n2)，大大降低了算法时间复杂度。因为八数码的输入是9位而BFS肯定要搜索9的全排列，(9!\*9!)就炸了，而(9!\*81)=29,393,280，吁~刚刚好！

我这里真是懒得手敲康托展开的过程，我来几张书的扫描图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

参考书：《算法竞赛从入门到进阶》

## 答案代码 ##

#include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    struct node
    { 
        int state[9];
        int dis;
    };
    const int LEN = 362880;
    int dir[4][2] = { { -1, 0}, { 0, -1}, { 1, 0}, { 0, 1}};
    
    int visited[LEN] = { 0};
    int start[9];
    int goal[9] = { 1, 2, 3, 8, 0, 4, 7, 6, 5}; // 因为题目而改
    long int factory[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
    
    bool Cantor(int str[], int n)
    { 
        long result = 0;
        for (int i = 0; i < n; i++)
        { 
            int counted = 0;
            for (int j = i + 1; j < n; j++)
            { 
                if (str[i] > str[j])
                    ++counted;
            }
            result += counted * factory[n - i - 1];
        }
        if (!visited[result])
        { 
            visited[result] = 1;
            return 1;
        }
        else
        { 
            return 0;
        }
    }
    
    int bfs()
    { 
        node head;
        memcpy(head.state, start, sizeof(head.state));
        head.dis = 0;
        queue<node> q;
        Cantor(head.state, 9);
        q.push(head);
    
        while (!q.empty())
        { 
            head = q.front();
            if (memcmp(head.state, goal, sizeof(goal)) == 0)
                return head.dis;
            q.pop();
            int z;
            for (z = 0; z < 9; z++)
            { 
                if (head.state[z] == 0)
                    break;
            }
            int x = z % 3;
            int y = z / 3;
            for (int i = 0; i < 4; i++)
            { 
                int newx = x + dir[i][0];
                int newy = y + dir[i][1];
                int nz = newx + 3 * newy;
                if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3)
                { 
                    node newnode;
                    memcpy(&newnode, &head, sizeof(struct node));
                    swap(newnode.state[z], newnode.state[nz]);
                    newnode.dis++;
                    if (Cantor(newnode.state, 9))
                        q.push(newnode);
                }
            }
        }
        return -1;
    }
    int main()
    { 
        int n, i = 8;
        cin >> n;
        while (i >= 0)
        { 
            start[i] = n % 10;
            n /= 10;
            i--;
        }
        // for (int i = 0; i < 9; i++)
        // cin >> start[i]; 因为题目而改
        // for (int i = 0; i < 9; i++)
        // cin >> goal[i];
        int num = bfs();
        if (num != -1)
            cout << num << endl;
        else
            cout << "Impossible" << endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/067de02207704d31bf70a8cd973f3253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221023/7179e653534d447abdd022e905096cc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221023/55300e6a20a84854946f468964170955.png