[cdoj1380] Xiper的奇妙历险(3) (八数码问题 bfs + 预处理)

快要NOIP 2016 了，现在已经停课集训了。计划用10天来复习以前学习过的所有内容。首先就是搜索。

八数码是一道很经典的搜索题，普通的bfs就可求出。为了优化效率，我曾经用过康托展开来优化空间，甚至还用过A*来优化时间。不过这道题懒得写了，就一个普普通通的bfs，再加上一个stl 的map就水过了。

首先题目要求有多达10000组数据，依次搜索肯定是不行的，我试过用A*来写，第2组数据就会T掉，所以我们考虑用一个预处理。从末尾状态搜索所有可行的状态，并用一个map来存储答案。然后就很好写了。

不过最智障的是，我用getchar读入数据，手测数据都对，交上去wa了无数次，改了快一晚上才发现是读入挂了。辣鸡getchar

#include <iostream>
#include <map>
#include <queue>
#include <cstdio> 
using namespace std;
typedef pair <int ,int> pis;
#define OK(a,b) (a < 3 && a >= 0 && b < 3 && b >= 0)

int t;
map <long long, int > MAP;
queue <pis > q;

int mx[] = {1,-1,0,0};
int my[] = {0,0,-1,1};

inline int E(int x){return x==0 ? 1 : 10 * E(x-1);}

inline void bfs(){
    int u = 123456780;
    int p;
    MAP[u] = 1;
    q.push(make_pair(u,8));
    while(!q.empty()){
        u = q.front().first; p = q.front().second;q.pop();
        int x = p / 3, y = p % 3;
        for(int i = 0;i < 4;i++){
            int nx = x + mx[i];
            int ny = y + my[i];
            if(OK(nx,ny)){
                int nu = u;
                int xx = (nu % E(9-(nx * 3 + ny))) / E(8-(nx * 3 + ny));
                nu -= xx * E(8-(nx * 3 + ny));
                nu += xx * E(8-p);
                if(!MAP[nu]){
                    MAP[nu] = MAP[u] + 1;
                    q.push(make_pair(nu,nx*3+ny));
                }
            }
        }
    }
    
}

int main(){
    bfs();
    
    scanf("%d",&t);
    char s[9];
    while(t--){
        int m = 0;
        for(int i = 0;i < 9;i++){
            scanf("%s",s);
            m = m * 10 + (s[0] == 'x' ? 0 : (s[0] - '0'));
        }
        printf("%d
",MAP[m] - 1);
    }
    
    return 0; 
}