AOJ 0121 广度优先搜索

题意：7数码问题。在2×4的棋盘上，摆有7个棋子，每个棋子上标有1至7的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（用0表示），与空格相邻（上下左右）的棋子可以移到空格中，该棋子原先位置成为空格。给出一个初始状态（保证可以转移到最终状态），找出一种从初始状态转变成给定最终状态的移动棋子步数最少的移动步骤。

输入：多组输入，每组8个数，表示初始状态前四个数为第一行从左到右，后四个数为第二行从左到右。 

输出：至少需要多少步可以从输入状态到达最终状态（0 1 2 3 4 5 6 7） 

（题意翻译参考自http://bbs.byr.cn/#!article/ACM_ICPC/73337?au=Milrivel）

（图1）

　　(图2)

　　（图3）

分析：

乍一看这题没从入手，但只要采取逆向思维，还是可以用广度优先搜索解决。先不考虑如何用最小步数从输入状态到达最终状态，所有结果的最终状态都是（01234567），那么反过来想，只要求出最终状态到达所有结果时的最小步数并记录下来，接下来就是查表了。0表示空位置，对空位置周围的格子采用广度优先的方式移动到0，并记录下最小步数的结果即可。如上图所示，图1，可以选择让7移动过来变成图2，也可以选择让2移动过来变成图3。我们要做的只不过是不断重复这种选择，直至穷举所有情况并记录结果。

我主要是用一个map<string, int>来表示(01234567)到string 的最小步数int，只要当前结果还不存在，就加入map，必然能够穷尽状态。另外，在移动格子问题上，因为我采用string来表示当前状态，那么移动方向上下左右分别就是当前位置-4, +4, -1, +1。需要注意的是，位置3不能移动到位置4.

#include <iostream>
#include <queue>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

typedef pair<string, int> P;

const int INF = 100000000;

//输入
string a;

//移动方向
int op[4] = {-1, 1, -4, 4};

map<string, int> dp;                        //保存从string变到"01234567"的int

//计算从"01234567"转换到其他序列所需的最小步数
void bfs(){
    //初始化
    queue<P> que;
    que.push(P("01234567", 0));
    dp["01234567"] = 0;
    //宽度优先搜索
    while(!que.empty()){
        P p = que.front();
        que.pop();
        string s = p.first;
        int cur = p.second;
        for(int i = 0; i < 4; i ++){
            //构造下一次交换
            int next = cur + op[i];
            string str = s;
            swap(str[cur], str[next]);
            map<string, int>::iterator it = dp.find(str);
            //判断是否可移动以及是否访问过
            if(0 <= next && next < 8 
                && !(cur == 3 && next == 4) && !(cur == 4 && next == 3) 
                && it == dp.end()){

                que.push(P(str, next));
                dp[str] = dp[s] + 1;
            }
        }
    }
}

void solve(){
    //删除空格
    a.erase(remove(a.begin(), a.end(), ' '), a.end());
    cout<<dp[a]<<endl;
}

int main(int argc, char const *argv[]){
    //先逆向构造所有情况，后直接读取输入用例的结果
    bfs();
    while(getline(cin, a)){
        solve();
    }
    return 0;
}