题目描述

在一个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
把“X”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

样例

输入样例：
2  3  4  1  5  x  7  6  8

输出样例:
ullddrurdllurdruldr

这道题让我深切体会到unordered_map的强大,因为用map会超时!!!
其实这道题我用的纯广搜,直接扩展每一个状态;
至于输出方案,我们可以存一下每个状态是从哪个状态转移过来的,输出时倒找回去即可.

时间复杂度 $O(我依然不知道)$

C++ 代码

#include<bits/stdc++.h>
#define N 8
using namespace std;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//方向数组
char way[5]="udlr";//移动的方式,注意一定要和方向数组对应
string End="12345678x";//最终状态
unordered_map<string,int> state;//存当前状态是怎样从他的上一个状态转移过来的
unordered_map<string,string> pre;//存当前状态的上一个状态
inline bool check(int x,int y)//检查是否越界
{
    if(x<0||x>=3||y<0||y>=3)
        return false;
    return true;
}
inline bool BFS(string start)
{
    queue<string> q;
    q.push(start),state[start]=0;
    while(!q.empty()){
        string temp=q.front();
        q.pop();
        string now=temp;
        if(now==End)
            return true;
        int k=temp.find('x');
        int x=k/3,y=k%3;//计算x在原矩阵的位置
        for(int i=0;i<4;i++){
            int dx=x+dir[i][0],dy=y+dir[i][1];
            if(!check(dx,dy))
                continue;
            int t=dx*3+dy;
            swap(temp[k],temp[t]);
            if(!state.count(temp)){//如果没有扩展过当前状态
                state[temp]=i;
                pre[temp]=now;
                q.push(temp);
            }
            swap(temp[t],temp[k]);
        }
    }
    return false;
}
int main()
{
    string start,ch;
    for(int i=0;i<9;i++){
        cin>>ch;
        start+=ch;
    }
    if(BFS(start)){
        vector<char> Way;
        string now=End;
        while(now!=start){
            Way.push_back(way[state[now]]);
            now=pre[now];
        }
        for(int i=Way.size()-1;i>=0;i--)//倒序输出
            cout<<Way[i];
        printf("\n");
    }
    else
        printf("unsolvable\n");
    return 0;//完结撒花
}