历届试题 九宫重排

问题描述

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

输入格式

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

输出格式

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

样例输入

12345678. 123.46758

样例输出

3

样例输入

13524678. 46758123.

样例输出

22

思路：广搜嘛，我把  .  改成了9，然后存到了一个int里面，这样省空间

但其实用9个char来存更快，不过空间支出大一点，也没啥关系啦。

也许还有更骚的操作，请大家自行开发啦

#include
#include
#include
#include
#include
#include
#include
using namespace std;
int start, End, poi;
typedef struct state
{
    int start, poi, bushu;
}state;
queue q;
set c;
int ci[9] = { 100000000,10000000,1000000,100000,10000,1000,100,10,1 };
int swap(int start, int p1, int p2)
{
    int t1, t2;
    t1 = start / ci[p1]%10;
    start -= (t1*ci[p1]);
    t2 = start / ci[p2]%10;
    start -= (t2*ci[p2]);
    start += (t1*ci[p2]);
    start += (t2*ci[p1]);
    return start;
}
int bfs()
{
    state s = q.front();
    while (!q.empty() && s.start != End)
    {
        state temp;
        if (s.poi / 3>0)
        {
            temp.start = swap(s.start, s.poi, s.poi - 3);
            temp.poi = s.poi - 3;
            temp.bushu = s.bushu + 1;
            if (!c.count(temp.start))
            {
                q.push(temp);
                c.insert(temp.start);
            }
        }
        if (s.poi % 3 != 2)
        {
            temp.start = swap(s.start, s.poi, s.poi + 1);
            temp.poi = s.poi + 1;
            temp.bushu = s.bushu + 1;
            if (!c.count(temp.start))
            {
                q.push(temp);
                c.insert(temp.start);
            }
        }
        if (s.poi / 3<2)
        {
            temp.start = swap(s.start, s.poi, s.poi + 3);
            temp.poi = s.poi + 3;
            temp.bushu = s.bushu + 1;
            if (!c.count(temp.start))
            {
                q.push(temp);
                c.insert(temp.start);
            }
        }
        if (s.poi % 3 != 0)
        {
            temp.start = swap(s.start, s.poi, s.poi - 1);
            temp.poi = s.poi - 1;
            temp.bushu = s.bushu + 1;
            if (!c.count(temp.start))
            {
                q.push(temp);
                c.insert(temp.start);
            }
        }
        q.pop();
        s = q.front();
    }
    if (q.empty())return -1;
    return s.bushu;
}
int main()
{
    state s;
    s.bushu = 0; s.poi = poi;
    string a;
    cin >> a;
    for (int i = 0; i != 9; i++)
        if (a[i] == '.')
        {
            s.poi = i;
            a[i] = '9';
        }
    int ans = 0;
    for (int i = 0; i != a.length(); i++)
    {
        ans *= 10;
        ans += (a[i] - '0');
    }
    s.start = ans;
    cin >> a;
    for (int i = 0; i != 9; i++)
        if (a[i] == '.')a[i] = '9';
    ans = 0;
    for (int i = 0; i != a.length(); i++)
    {
        ans *= 10;
        ans += (a[i] - '0');
    }
    End = ans;
    q.push(s);
    int cnt = bfs();
    cout << cnt << endl;
    return 0;
}