题目描述
在一个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：bfs 时间复杂度 O(9!) 8000 ms
直接进行bfs
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
string s;
string e = "12345678x";
unordered_map<string,int> dist;
unordered_map<string,pair<char,string> > pre;
int dx[4] = {-1,1,0,0},dy[4]={0,0,-1,1};
char op[4] = {'u','d','l','r'};
int get(string str)
{
for(int i=0;i<str.size();i++)
if(str[i] == 'x')
return i;
return -1;
}
bool bfs(){
queue<string> q;
q.push(s);
dist[s] = 0;
while(q.size())
{
string t = q.front();
q.pop();
if(t==e) return true;
int p = get(t);
int d = dist[t];
int x = p/3 , y = p%3;
string temp = t;
for(int i=0;i<4;i++)
{
int a = x + dx[i];
int b = y + dy[i];
if(a>=0&&a<3&&b>=0&&b<3)
{
t = temp;
swap(t[3*a+b],t[3*x+y]);
if(dist.count(t)==0)
{
dist[t] = d + 1;
pre[t] = {op[i],temp};
q.push(t);
}
}
}
}
return false;
}
int main(){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
for(int i=0;i<9;i++)
{
char x[2];
cin >> x;
s += x[0];
}
if(!bfs()) puts("unsolvable");
else {
string res;
while(e!=s)
{
res += pre[e].first;
e = pre[e].second;
}
reverse(res.begin(),res.end());
cout << res << endl;
}
return 0;
}
解法2 A* 时间复杂度O(?) 140ms
先把无解的情况给给判断掉，判无解就是求逆序对，《算法进阶指南》第0x05奇数码这题中讲的还是挺详细的，把无解情况规避掉A*就能发挥他超快的运作效率了。
代价函数为所有点到他终态的（除了x）曼哈顿距离，为什么这是对的？
摘自《算法竞赛进阶指南》：每次移动只能把一个数字与空格交换位置，这样至多把一个数字向它在终态中的位置移进一步。即使每一步都是有意义的，从任何一个状态到目标状态的移动步数也不可能小于所有数字当前位置与目标位置的曼哈顿距离之和。
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <cmath>
#define pis pair<int,string>
using namespace std;
string s,e="12345678x";
unordered_map<string,int> dist;
unordered_map<string,pair<char,string> > pre;
int dx[4] = {-1,1,0,0},dy[4]={0,0,-1,1};
char op[4] = {'u','d','l','r'};
int get(string str){
for(int i=0;i<str.size();i++)
if(str[i] == 'x')
return i;
return -1;
}
int f(string str)
{
int res = 0;
for(int i=0;i<str.size();i++)
if(str[i]!='x')
{
int value = str[i] - '1';
int a = value / 3 , b = value % 3;
int x = i / 3 ,y = i % 3;
res += abs(a-x) + abs(b - y);
}
return res;
}
void bfs()
{
priority_queue<pis,vector<pis>,greater<pis> > heap;
heap.push({f(s),s});
dist[s] = 0;
while(heap.size())
{
string t = heap.top().second;
heap.pop();
if(t==e) return;
int d = dist[t];
int p = get(t);
int x=p/3,y=p%3;
string temp = t;
for(int i=0;i<4;i++)
{
int a = x + dx[i],b = y + dy[i];
if(a>=0&&a<3&&b>=0&&b<3)
{
t = temp;
swap(t[3*a+b],t[3*x+y]);
if(dist.count(t) == 0 || dist[t] > d + 1)
{
dist[t] = d + 1;
pre[t] = {op[i],temp};
heap.push({d + 1 + f(t),t});
}
}
}
}
}
int main(){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
string str;
for(int i=0;i<9;i++)
{
char x[2];
cin >> x;
s += x[0];
if(x[0] != 'x')
str += x[0];
}
int cnt = 0;
for(int i = 0;i < str.size();i++)
for(int j = i + 1;j < str.size();j++)
if(str[j]<str[i])
cnt ++;
if(cnt & 1) puts("unsolvable");
else
{
bfs();
string res;
while(e!=s)
{
res += pre[e].first;
e = pre[e].second;
}
reverse(res.begin(),res.end());
cout << res << endl;
}
return 0;
}
dalao