注意此处提供了链接
1. 八数码
问题描述
在一个$3×3$的网格中，$1\sim 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-8每个数和最终位置的曼哈顿距离之和*/
/*string,map<string,int>*/
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
int dir[4][2]={-1,0,1,0,0,-1,0,1};
char op[4]={'u','d','l','r'};
int f(string state)
{
int res;
for(int i=0;i<state.size();i++)
if(state[i] !='x')
{
int t=state[i]-'1';
res+=abs(i/3-t/3)+abs(i%3-t%3);
}
return res;
}
string bfs(string start)
{
string end1="12345678x";
unordered_map<string,int> dist;//当前状态所需要距离
unordered_map<string,bool> st;//当前状态是否被搜过
unordered_map<string,pair<string,char>> prev;//记录上一个状态以及接下来的操作
priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>> heap;
heap.push({f(start),start});
dist[start]=0;
while(heap.size()>0)
{
auto t=heap.top();
heap.pop();
string state=t.second;
if(state==end1)
break;
if(st[state]!=0)
continue;
st[state]=true;
int step=dist[state];
int x,y;
for(int i=0;i<state.size();i++)
if(state[i]=='x')
{
x=i/3;
y=i%3;
break;
}
string source=state;
for(int i=0;i<=3;i++)
{
int a=x+dir[i][0],b=y+dir[i][1];
if(a>=0&&a<=2&&b>=0&&b<=2)
{
swap(state[x*3+y],state[a*3+b]);
if(!dist.count(state)||dist[state]>step+1)
{
dist[state]=step+1;
prev[state]={source,op[i]};
heap.push({dist[state]+f(state),state});
}
swap(state[x*3+y],state[a*3+b]);
}
}
}
string res;
while(end1!=start)
{
res+=prev[end1].second;
end1=prev[end1].first;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
string g,c,seq;
while(cin >> c)
{
g+=c;
if ( c != "x" )
seq+=c;
}
//printf("%s\n%s\n%s",g,c,seq);
int t=0;
for(int i=0;i<seq.size();i++)
for(int j=i+1;j<seq.size();j++)
if(seq[i]>seq[j])
t++;
if(t%2==1)
printf("unsolvable\n");
else
cout << bfs(g) << endl;
return 0;
}
