蓝桥杯 历届试题 九宫重排

时间:2021-01-30 09:49:51
登录后才能查看试题。

  历届试题 九宫重排  

时间限制:1.0s   内存限制:256.0MB

   


锦囊1

锦囊2

锦囊3

问题描述

  如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。
蓝桥杯 历届试题 九宫重排蓝桥杯 历届试题 九宫重排
  我们把第一个图的局面记为:12345678.
  把第二个图的局面记为:123.46758
  显然是按从上到下,从左到右的顺序记录数字,空格记为句点。
  本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。

输入格式

  输入第一行包含九宫的初态,第二行包含九宫的终态。

输出格式

  输出最少的步数,如果不存在方案,则输出-1。

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22

#include <queue>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 1000000;
int str[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
char direction[5] = "udlr";
int fac[] = {1,1,2,6,24,120,720,5040,40320,362880}; //这里就是从0的阶乘到9的阶乘
int vis[maxn],aim;

struct Node
{
int s[9];
int loc;
int status;
int step;
string path;
}pre,cur;

int cantor(int *s) //康拓展开
{
int ans = 0;
for(int i = 0; i < 9; i++)
{
int num = 0;
for(int j = i+1; j < 9; j++)
if(s[i] > s[j]) num++;
ans += (fac[9-i-1]*num);
}
return ans+1;
}

void BFS()
{
memset(vis,0,sizeof(vis));
queue <Node> q;
vis[pre.status] = 1;
q.push(pre);
while(!q.empty())
{
pre = q.front(); q.pop();
int x = pre.loc/3;
int y = pre.loc%3;
if(pre.status == aim)
{
printf("%d\n",pre.step);
return;
}
for(int i = 0; i < 4; i++)
{
int xx = x + str[i][0];
int yy = y + str[i][1];
if(xx < 0 || xx >= 3 || yy < 0 || yy >= 3)
continue;
cur = pre;
cur.loc = xx*3 + yy;
cur.s[pre.loc] = cur.s[cur.loc];
cur.s[cur.loc] = 0;
cur.status = cantor(cur.s);
if(!vis[cur.status])
{
++cur.step;
vis[cur.status] = 1;
cur.path = direction[i] + cur.path;
q.push(cur);
}
}
}
}

int main()
{
char a[10];
while(scanf("%s", a) != EOF)
{
for(int i = 0; i < 9; i++)
{
if(a[i] == '.')
{
pre.s[i] = 0;
pre.loc = i;
}
else
pre.s[i] = a[i] - '0';
}
pre.status = cantor(pre.s);
pre.step = 0;
scanf("%s", a);
for(int i = 0; i < 9; i++)
{
if(a[i] == '.')
cur.s[i] = 0;
else
cur.s[i] = a[i] - '0';
}
aim = cantor(cur.s);
BFS();
}
return 0;
}