A40964. 九宫重排
填空题
困难
知识点
题目描述
九宫重排
题目描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
样例输出
3
参考答案
#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <queue>
using namespace std;
map<string,int> mp; //用于存储某种情况是否出现过
int change[4]={3,-3,-1,1};
struct node
{
string s;
int step;
}first; //初始状态
queue<node> q;
int n,move_;
char temp;
string temp_s;
int check(int u, int v) //u起点,v终点
{
if (v < 0 || v>8) return 0;
if (v == u - 1) //如果是左移一位，必须保证起点不在第一列
{
if (u == 0 || u == 3 || u == 6) return 0;
}
if (v == u + 1) //如果是右移一位,必须保证起点不在最后一列
{
if (u == 2 || u == 5 || u == 8) return 0;
}
return 1; //都不会违规就返回1
}
int find_(string ss)
{
if(mp.count(ss)) return 0; //如果已存在
return 1;
}
int main()
{
string s_first, s_last;
cin >> s_first >> s_last;
first.s = s_first; //初始状态,步数为0
first.step = 0;
q.push(first); //将队首压入队列
mp[first.s]=1;
while (!q.empty())
{
node a = q.front(); //建一个新节点等于队头
node t = a;
q.pop(); //出队
if (a.s == s_last)
{
cout << a.step;
return 0;
}
for (int i = 0; i < a.s.size(); i++) //寻找.的位置
{
if (a.s[i] == '.') n = i;
}
for(int i=0;i<4;i++)
{
if(check(n,n+change[i]))
{
a=t;
move_=change[i];
temp_s=a.s;
temp=temp_s[n+move_]; //取出要交换的字符,交换两个格子
temp_s[n+move_]=temp_s[n];
temp_s[n]=temp;
if(find_(temp_s)) //如果这种情况没有出现过就进行真正的交换
{
temp=a.s[n+move_];
a.s[n+move_]=a.s[n];
a.s[n]=temp; //交换
a.step++;
mp[a.s]=1; //标记
q.push(a); //将a入队
}
}
}
}
cout << "-1";
return 0;
}
上一题
下一题