蓝桥杯 历届试题-九宫重排

时间：2021-01-30 09:49:45

问题描述

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

解题思路

看起来非常像一个全排列问题，但这道题不是。
首先这道题要求的状态的转换是有限制要求的，即每一次移动只能移动空格和空格的上下左右，且与他移动的还必须存在，即不能越界。其次这道题要求的是最短路径，想到这里就很明显了，把当前9个数的位置信息当成一个节点，通过移动格子能转换到的状态也就是他的邻接点，把它当成一副图用bfs来做就ok了。
不过要注意一点就是其实不需要建图，每一个状态的相邻节点都能通过空格的位置推出。
不过这道题有一个坑点，如何判断一个节点是否已经访问过，这很重要，如果没法判断，那么程序一旦碰到环就会死循环，那就建个数组标记一下，可是怎么标记啊，一个节点有9个信息，总不能用9维的数组吧。所以一个好的解决方法就是用散列表，这样问题就解决了。
程序要求最小步数，那么就在第一次访问到每一节点时标记一下从谁访问的，最后直接从终止节点开始一路推到开始节点就可以了。

代码

#include <iostream>
#include <cstring>

#define QMAX 370000

#define HASHMAX 10000

int htable[HASHMAX];

int next[QMAX];

int queue[QMAX][9];

int zeros[QMAX];

int vis[QMAX];

int front;
int rear;

int result[9];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int pre[QMAX];

int hash(int pos)
{
int h = 0;
for(int i = 0; i < 9; i++)
    {
        h = h*10+queue[pos][i];
        h%=HASHMAX;
    }

return h;
}

bool insert(int pos)
{
int h = hash(pos);
for(int n = htable[h]; n!=-1; n=next[n])
    {
if(memcmp(queue[n], queue[pos], sizeof(int)*9) == 0)
return false;     
    }

    next[pos] = htable[h];
    htable[h] = pos;
return true;
}


int bfs()
{
    pre[0] = -1;
while(front < rear)
    {
int *cur = queue[front++];
if(memcmp(cur, result, sizeof(int)*9) == 0)
return front-1;
int zx = zeros[front-1]/3;
int zy = zeros[front-1]%3;

for(int i = 0; i < 4; i++)
        {
int nx = zx+dx[i];
int ny = zy+dy[i];

if(nx < 0 || nx >=3 || ny < 0 || ny >= 3)
continue;
int (*next)[3] = (int (*)[3])queue[rear++];
memcpy((int *)next, cur, sizeof(int)*9);
            next[zx][zy] = next[nx][ny];
            next[nx][ny] = 0;
            zeros[rear-1] = nx*3+ny;
            pre[rear-1] = front-1;
if(!insert(rear-1))
                rear--;
        }

    }
return -1;
}

int main()
{

memset(htable, -1, sizeof(htable));
for(int i = 0; i < 9; i++)
    {
char ch;
std::cin >> ch;
if(ch == '.') {
queue[rear][i] = 0;
            zeros[rear] = i;
        }
else
queue[rear][i] = ch-'0';
    }
    rear++;

for(int i = 0; i < 9; i++)
    {
char ch;
std::cin >> ch;
if(ch == '.')
            result[i] = 0;
else
            result[i] = ch-'0';
    }

int tot = -1;

for(int p = bfs(); p!=-1; p=pre[p])
        tot++;

std::cout << tot << std::endl;
}

总的来说这道题就是一个水题，虽然当时自己也做了半天。现在看来这道题其实内容很简单，一个无向无权图的最短路径，直接用bfs就能解决，但这中间会碰到一些问题，像用散列表实现标记数组，还是挺有意思的。

标签：

相关文章