蓝桥杯 历届试题 九宫重排

登录后才能查看试题。

  历届试题 九宫重排  

时间限制：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;
}