AcWing - 179.八数码

传送门：AcWing - 179

题目描述

在一个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”与上下左右方向数字交换的行动记录为“u”、“d”、“l”、“r”。
现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入描述

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

输出描述

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

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

思路分析

对于这类问题，我们知道一个结论，如果去除空格将数排列起来，如果逆序对的个数为奇数，那么肯定无解，那么对于有解的情况，这道题可以用普通的BFS做，这里用的是A*算法，定义一个估价函数，即每一个数到它正确的位置的曼哈顿距离之和。

样例输入

2  3  4  1  5  x  7  6  8 

样例输出

ullddrurdllurdruldr

AC代码

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;

int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char op[4]={'d','u','r','l'};

int f(string s){
    int sum=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!='x'){
            int t=s[i]-'1';
            sum+=abs(i/3-t/3)+abs(i%3-t%3);
        }
    }
    return sum;
}

string Astar(string st){
    
    string end="12345678x";
    umap<string,int>dis;
    umap<string,bool>vis;
    umap<string,pair<string,char>>pre;
    priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>> q;
    dis[st]=0;
    q.push({f(st),st});
    while(!q.empty()){
        auto t=q.top();
        q.pop();
        string now=t.se;
        if(now==end)
            break;
        if(vis[now])
            continue;
        vis[now]=true;
        int step=dis[now];
        
        int x,y;
        for(int i=0;i<now.size();i++){
            if(now[i]=='x'){
                x=i/3;
                y=i%3;
                break;
            }
        }
        string u=now;
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if( nx>=0 && nx<3 && ny>=0 && ny<3){
                swap(now[x*3+y],now[nx*3+ny]);
                if(!dis.count(now)||dis[now]>step+1){
                    dis[now]=step+1;
                    pre[now]={u,op[i]};
                    q.push({dis[now]+f(now),now});
                }
                swap(now[x*3+y],now[nx*3+ny]);
            }
        }
    }
    string ans;
    while(end!=st){
        ans+=pre[end].se;
        end=pre[end].fi;
    }
    reverse(ans.begin(),ans.end());
    return ans;
    
} 

int main() {
    string a,b,c;
    while(cin>>b){
        a+=b;
        if(b!="x")
            c+=b;
    }
    int t=0;
    for(int i=0;i<c.size();i++)
        for(int j=i+1;j<c.size();j++)
            if(c[j]<c[i])
                t++;    
    if(t&1)
        puts("unsolvable");
    else 
        cout<<Astar(a)<<endl;
    
    return 0;
}