题目描述
在一个 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
输出格式
输出占一行,包含一个字符串,表示得到正确排列的完整行动记录。
如果答案不唯一,输出任意一种合法方案即可。
如果不存在解决方案,则输出 unsolvable。
输入样例:
2 3 4 1 5 x 7 6 8
输出样例
ullddrurdllurdruldr
思路和字符变换 差不多
一条从start开始搜,另一边从end开始搜
先算逆序对确保有解
当搜到的 st在另一队中存在,则返回;
注意的点
start 到 temp 只需要反转操作字符串
而temp 到 end 需要反转操作字符例如 把 u->d, l -> r
算法1
(双向广搜)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <set>
#define x first
#define y second
using namespace std;
string start,seq,temp1;
char op[] ="udrl";
int dx[4] = {-1,1,0,0},dy[4] ={0,0,1,-1};
string ans;
bool extend(queue<string>&q,set<string>&da,set<string>&db,unordered_map<string,pair<string,char>>&pre)
{
int x,y;
string st,source;
int a,b;
{
st = q.front();
q.pop();
//确定坐标
for(int i = 0;i < 9;i++)
if(st[i] == 'x')
{
x = i / 3,y = i % 3;
break;
}
source = st;
for(int i = 0;i < 4;i++)
{
a = x + dx[i],b = y + dy[i];
st = source;
if(a < 0 || a >= 3 || b < 0 || b >= 3) continue;
swap(st[3*a + b],st[3*x + y]);
if(da.count(st)) continue;
q.push(st);
pre[st] = {source,op[i]};
da.insert(st);
if(db.count(st)){
seq = st;
temp1 = st;
return 1;
//在另一队中找到则返回
}
}
}
return false;
}
void bfs()
{
string end = "12345678x";
set<string>da,db;
queue<string>qa,qb;
unordered_map<string,pair<string,char>>prea,preb;
qa.push(start);
qb.push(end);
bool t;
while(qa.size() && qb.size())//qa.size() && qb.size()
{
if(qa.size() < qb.size()) t = extend(qa,da,db,prea);
else t = extend(qb,db,da,preb);
if(t) break;
}
{
string temp2;
string op_front ,op_end;
//seq = temp1;
temp2 = seq;
while(seq != start)
{
op_front += prea[seq].y;
// cout << seq << endl;
seq = prea[seq].x;
}
//从开始到中间要反转操作字符串
reverse(op_front.begin(),op_front.end());
seq = temp1;
while(seq != end)
{
op_end+= preb[seq].y;
//cout << seq << endl;
seq = preb[seq].x;
}
//反转操作字符
for(int i = 0;i < op_end.size();i++)
{
if(op_end[i] == 'u'){
op_end[i] = 'd';
continue;
}
if(op_end[i] == 'd'){
op_end[i] = 'u';
continue;
}
if(op_end[i] == 'l'){
op_end[i] = 'r';
continue;
}
if(op_end[i] == 'r'){
op_end[i] = 'l';
continue;
}
}
cout << op_front <<op_end<<endl;
}
}
int main()
{
char c;
while(cin >> c)
{
start += c;
if(c !='x') seq += c;
}
int sum = 0;
for(int i = 0; i < 8;i++)
for(int j = i;j < 8;j++)
if(seq[j] > seq[i]) sum++;
if(sum & 1){
puts("unsolvable");
return 0;
}
bfs();
return 0;
}
/*
int find(char str[],char c){
int res = 0;
while(1){
if(str[res] == c) return res;
res++;
}
}
*/
//uldddldulldluu
//ullddrurdllurrdlurd
//4267x1385
//415672x83
//6 4 7 8 5 x 3 2 1
//415x72683