题目描述

在一个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”。

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

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

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

x 4 6

7 5 8

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

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。如果答案不唯一，输出任意一种合法方案即可。

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

样例

输入样例：

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

ullddrurdllurdruldr

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string a;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
char dch[4]={'d','l','u','r'};
int c[100];
unordered_map<string,bool> mp;

struct node{
    string st;
    string ans;
};
node t;
string b;
queue<node>q;

int main(){
    a="";
    for (int i=1;i<=9;i++)
    {
        cin>>b;
        if (b=="x") c[i]=0;
        else c[i]=b[0]-48;
        a+=b;
    }
    int tot=0;
    for (int i=1;i<=9;i++)
        for (int j=i+1;j<=9;j++)
        {
            if (c[i]==0||c[j]==0) continue;
                if(i<j&&c[i]>c[j]) tot++;
        }
    if (tot%2) 
    {   
        cout<<"unsolvable\n";
        return 0;
    }
    t.st=a;
    t.ans="";
    q.push(t);
    int num,nnum,nx,ny;

    while(!q.empty())
    {
        node nt=q.front();
        num=nt.st.find('x');
        for(int i=0;i<4;i++)
        {
            nx=num/3;
            ny=num%3;
            nx+=dx[i];
            ny+=dy[i];
            if (nx<0||nx>2||ny<0||ny>2) continue;
            nnum=nx*3+ny;
            t=nt;
            t.st[num]=t.st[nnum];
            t.st[nnum]='x';
            t.ans+=dch[i];
            if (mp[t.st]==true) continue;
            mp[t.st]=true;
            if (t.st=="12345678x")
                {
                    cout<<t.ans<<endl;
                    return 0; 
                }
            q.push(t);

        }
        q.pop();
    }

    return 0;
}

Tips

如果要输出次数，把程序第64行改成 cout<<t.ans.size()<<endl; 再把第36行改成 cout<<”-1\n”; 就好了