题目描述
在一个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(不知道)$
宽度优先搜索,搜索过程中存下每个字符串的夫串和移动方式,得到最终状态后根据夫串依此向前搜索,得到移动方式
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
char d[5] = "drul"; //根据p[i]得到移动方式
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
string ed = "12345678x";
unordered_map<string, int> p;
unordered_map<string, string> pp;
bool bfs(string s)
{
queue<string> q;
q.push(s);
p[s] = 0;
while (q.size()) //宽度优先搜索
{
string sh = q.front();
q.pop();
string h = sh;
if (sh == ed) return true;
int k = sh.find('x');
int x = k / 3, y = k % 3; //求出坐标
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)
{
int t = a * 3 + b;
swap(sh[k], sh[t]);
if (!p.count(sh))
{
p[sh] = i; //存下移动方式
pp[sh] = h; //存下夫串
q.push(sh);
}
swap(sh[t], sh[k]);
}
}
}
return false;
}
int main()
{
string s, c;
for (int i = 0; i < 9; i ++ ) cin >> c, s += c;
if (bfs(s))
{
vector<char> arr;
string t = ed;
while(t != s)
{
arr.push_back(d[p[t]]); //将移动方式存下
t = pp[t];
}
for (int i = arr.size() - 1; i >= 0; i -- )
cout << arr[i];
cout << endl;
}
else cout << "unsolvable" << endl;
return 0;
}
啥是夫串?
啥是夫串?
秒哇,又借助一个unordered_map
bfs复杂度感觉分析出来也没啥用