Aizu 0121 Seven Puzzle

Description

给你一个4x2的方版，上面有0-7 八个数字，每次只能让编号0的方格跟他的上下左右的方格交换；所以也就是把方格0当做空格看待，每次只有空格周围的方格能够向空格处移动。 然后问从输入的方格样式变换到字典序最小的”01234567” 最少需要多少次.

Idea

https://cn.vjudge.net/problem/Aizu-0121

多组输入易超时的题：打表O（1）查询

打表：反向BFS，求出“01234567”到其他排列的最小步数

Code

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

map<string, int> mp;
map<string, bool> vis;
int dir[] = {1, -1, 4, -4};

struct node
{
    string s;
    int zero, step;
};

void BFS()
{
    string ch = "01234567";
    mp[ch] = 0;
    vis[ch] = 1;
    node now, nxt;
    now.s = ch, now.zero = 0, now.step = 0;
    queue<node> q;
    q.push(now);
    while(q.size())
    {
        now = q.front();
        q.pop();


        for(int i = 0; i < 4; ++i)
        {
            int pos = now.zero + dir[i];
            if((pos < 0 || pos > 7) || (pos == 3 && now.zero == 4) || (pos == 4 && now.zero == 3))
                continue;
            string t = now.s;
            swap(t[now.zero], t[pos]);
            if(vis[t] == 0)
            {
                vis[t] = 1;
                nxt.s = t;
                nxt.zero = pos;
                nxt.step = now.step + 1;
                q.push(nxt);
                mp[t] = nxt.step;///make the table
            }
        }
    }
}

int main()
{
    BFS();
    char tem[20];
    while(~scanf("%c", &tem[0]))
    {
        for(int i = 1; i < 8; ++i)
            getchar(), tem[i] = getchar();
        getchar();
        tem[8] = '\0';//堵光标
        cout << mp[tem] << '\n';
    }
    return 0;
}