菜鸡来混一发题解

题目描述

在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。

例如：

1 2 3
X 4 6
7 5 8

在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X

例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式
输入占一行，将3×3的初始网格描绘出来。

例如，如果初始网格如下所示：
1 2 3

x 4 6

7 5 8

则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出”-1”。

输入样例：

2  3  4  1  5  x  7  6  8 

输出样例

19

参考了滑稽大佬的题解ORZ https://www.acwing.com/solution/acwing/content/2481/

感谢倒计时0天 的debug ORZ

分析：

由于让我们求的是最少交换次数，可以想到用BFS来做，但是这道题和走迷宫问题还不太一样。
这道题的状态表示比较复杂，而且如何记录每个状态到初始状态的距离也是个问题。

1、如何表示状态：用pair或者unordered_map记录当前的字符串和步数，如果string是目标状态，那么返回步数。
预处理：把格子中的’x’换成‘9’

2、由于要保证BFS每一个状态只能访问被遍历过一次，那么就需要判重。如果使用的是unordered_map，用自带的count函数判重即可。
但是好多比赛不让用unordered_map.......例如：蓝桥杯
然后又学了康拓展开，简单介绍一下：

康拓展开：通俗点讲就是利用康拓展开公式，在一个全排列中找到当前的排列排第几，也就是说全排列中的每一个排列都会有一个数和它一一对应，利用这条性质就可以判重！
关于康拓展开的详细内容可以参考百度百科： 康拓展开

康拓展开的一般写法

/**
 * 例如：在 1 2 3 4 5 全排列中求出 3 4 1 5 2 排在第几
 * 
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int f[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; //0~9的阶乘

int conton(int a[], int n)
{
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        for (int j = i + 1; j < n; j++)
        {
            if (a[j] < a[i])
                cnt++; //记录逆序的个数
        }
        ans += cnt * f[n - i - 1];//康拓展开公式
    }
    return ans;
}

int main()
{
    int a[] = {3, 4, 1, 5, 2};
    cout << conton(a, 5) << endl; //比34152小的组合有61个 34152排在第62
    return 0;
}

算法1 BFS + unordered_map

参考文献 算法基础课

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;

string start;
queue<string> q;
unordered_map<string, int> d; //存储当前状态到下一状态的距离
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

int bfs(string start)
{
    string end = "12345678x"; //记录最后一个状态
    d[start] = 0;
    q.push(start); //将初始状态加入队列

    while (!q.empty())
    {
        string t = q.front(); //取队头
        q.pop();

        int dis = d[t];

        if (t == end)
            return dis;

        //状态转移
        int k = t.find('x'); //找到x返回下标

        //将x的坐标转化为二维
        int x = k / 3; //行
        int y = k % 3; //列
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
            {
                swap(t[k], t[xx * 3 + yy]); //将二维坐标转化成一维
                if (!d.count(t))            //如果没有出现过当前状态
                {
                   d[t] = dis + 1;
                    q.push(t);
                }
                swap(t[k], t[xx * 3 + yy]); //恢复现场
            }
        }
    }
    return -1;
}

int main()
{
    char c;
    for (int i = 0; i < 9; i++)
    {
        cin >> c;
        start += c;
    }

    printf("%d", bfs(start));

    return 0;
}

算法2 BFS + 康拓展开

参考文献 算法基础课

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<string, int> PSI;
int f[10]; //存0~9的阶乘
string start;
queue<PSI> q;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; //偏移量
bool vis[400000];                                 //因为9!=362880

void fab() //计算0~9的阶乘
{
    f[0] = 1;
    for (int i = 1; i <= 9; i++)
    {
        f[i] = i * f[i - 1];
    }
}

int canton(string s, int n)
{
    int ans = 0;
    fab(); //计算出0~9的阶乘
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        for (int j = i + 1; j < n; j++)
        {
            if (s[j] < s[i])
                cnt++; //记录逆序的个数
        }
        ans += cnt * f[n - i - 1]; //康托展开公式
    }
    return ans + 1;
}

int bfs(string start)
{
    string end = "123456789"; //记录最后一个状态

    q.push({start, 0}); //将初始状态加入队列
    vis[canton(start, 9)] = true;

    while (!q.empty())
    {
        PSI t = q.front(); //取队头
        q.pop();

        int dis = t.second;

        if (t.first == end)
            return dis;

        //状态转移
        int k = t.first.find('9'); //找到x返回下标

        //将x的坐标转化为二维
        int x = k / 3; //行
        int y = k % 3; //列
        for (int i = 0; i < 4; i++)
        {
            int xx = x + dx[i], yy = y + dy[i];
            if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
            {
                swap(t.first[k], t.first[xx * 3 + yy]); //将二维坐标转化成一维
                if (!vis[canton(t.first, 9)])           //如果没有访问过当前状态
                {
                    vis[canton(t.first, 9)] = true;
                    //dis = t.second + 1;
                    t.second = dis + 1;
                    q.push(t); //把当前的状态加入队列
                }
                swap(t.first[k], t.first[xx * 3 + yy]); //恢复现场
            }
        }
    }
    return -1;
}

int main()
{
    char c;
    for (int i = 0; i < 9; i++)
    {
        cin >> c;
        if (c == 'x') //把'x'看成'9'即可 则最后一个状态就是'123456789'
            c = '9';
        start += c;
    }

    printf("%d", bfs(start));

    return 0;
}