题意:
给你一个3x3的矩阵,其中有一个空格不填数,其他空格从1-8随机填数。只能把空格上下左右的数移动到空格处。现要求排列出123456780的矩阵,问最少操作次数的情况下,每次操作的选择。(通常问操作次数)
(BFS)
样例
INPUT
2 3 4 1 5 x 7 6 8
OUTPUT
ullddrurdllurdruldr
思路:bfs,用map记录每个状态,不重复走同一个状态。并且每个状态也开个map记录前一个状态以及选择,最后输出
code:
#include<iostream>
#include<queue>
#include<map>
typedef long long LL;
using namespace std;
int mp[4][4];
map<int, int>pre;
map<int, bool>st;
map<int, char>step;
int k=0;
const int N = 1e5 + 10;
char ans[N];
bool can_move(int u, int x, int y)
{
int r=0, c=0; k = 0; char s;
for (int i = 3; i >= 1; i--)//先把u解构为矩阵
for (int j = 3; j >= 1; j--)
{
mp[i][j] = u % 10;
u /= 10;
if (mp[i][j] == 0)r = i, c = j;
}
int r1 = r, c1 = c;
r += x, c += y;
if (r >= 1 && r <= 3 && c >= 1 && c <= 3 ) {
swap(mp[r1][c1], mp[r][c]);
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
k = k * 10 + mp[i][j];//新的状态
if (!st[k]) {//没到过该状态
if (x == 1 && y == 0)step[k] ='d' ;//记录步骤
else if (x == 0 && y == 1)step[k] = 'r';
else if (x == -1 && y == 0)step[k] = 'u';
else if (x == 0 && y == -1)step[k] = 'l';
return true;
}
}
return false;
}
bool bfs(int t) {
queue<int>q;
q.push(t);
st[t] = true;
pre[t] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
int x[] = { 0,0,1,-1 }, y[] = { 1,-1,0,0 };//上下左右
for (int i = 0; i <= 3; i++)
{
if (can_move(u, x[i], y[i]))
{
q.push(k);
st[k] = true;
pre[k] = u;//记录前一个状态
}
if (k == 123456780) {
int cnt = 0;
for (int j = 123456780; j != 0;j = pre[j])
{
ans[cnt++] = step[j];//记录每个步骤
// cout << step[j];
}
// cout<<ans[cnt-1];
for (int j = cnt - 2; j>=0; j--)printf("%c",ans[j]);//注意从cnt-2开始,初始状态下的step为0(这里调了我好久QAQ)
/* for (int i = ne[t]; i != -1; i = ne[i])
{
cout << step[i];
}*/
return true;
}
}
}
return false;
}
int main() {
int t = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
{
char a;
cin >> a;
if (a != 'x')
{
mp[i][j] = a - '0';
}
else mp[i][j] = 0;
t = t * 10 + mp[i][j];//以int形式保存该状态
}
if (!bfs(t))cout << "unsolvable";
return 0;
}