描述

传送门：Aizu-0121 Seven Puzzle

7 パズルは 8 つの正方形のカードとこれらのカードがぴたりと収まる枠で構成されています。それぞれのカードには、互いに区別できるように 0, 1, 2, …, 7 と番号がつけられています。枠には、縦に 2 個、横に 4 個のカードを並べることができます。
7 パズルを始めるときには、まず枠にすべてのカードを入れます。枠のなかで 0 のカードだけは、上下左右に隣接するカードと位置を交換することができます。たとえば、枠の状態が図(a) のときに、0 のカードの右に隣接した、7 のカードと位置を交換すれば、図(b) の状態になります。あるいは、図(a) の状態から 0 のカードの下に隣接した 2 のカードと位置を交換すれば図(c) の状態になります。図(a) の状態で 0 のカードと上下左右に隣接するカードは 7 と 2 のカードだけなので、これ以外の位置の入れ替えは許されません。
ゲームの目的は、カードをきれいに整列して図(d) の状態にすることです。最初の状態を入力とし、カードをきれいに整列するまでに、必要な最小手数を出力するプログラムを作成してください。ただし、入力されたカードの状態からは図(d) の状態に移ることは可能であるとします。
入力データは、1 行に 8 つの数字が空白区切りで与えられます。これらは、最初の状態のカードの並びを表します。例えば、図(a) の数字表現は0 7 3 4 2 5 1 6 に、図(c) は 2 7 3 4 0 5 1 6 となります。

(a) 0 7 3 4 2 5 1 6 の場合
(b) 7 0 3 4 2 5 1 6 の場合

(c) 2 7 3 4 0 5 1 6 の場合

(d) 0 1 2 3 4 5 6 7 (最終状態)

输入描述

上記形式で複数のパズルが与えられます。入力の最後まで処理してください。与えられるパズルの数は 1,000 以下です。

输出描述

各パズルについて、最終状態へ移行する最小手数を１行に出力してください。

示例

输入

1
2
3

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0

输出

1
2
3

0
1
28

题解

题目大意

只有牌0才能和四周的牌交换，给定一个状态，求到图d状态最少需要多少步

思路

bfs反向处理打表，用map存入每个状态。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<string, int> P;
map<string, int> mp;
string str;
int op[] = {-1, 1, 4, -4};

void bfs(){
    queue<P> que;
    que.push(P("01234567", 0));
    mp["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 nex = cur + op[i];
            string tmp = s;
            swap(tmp[cur], tmp[nex]);
            map<string, int>::iterator it = mp.find(tmp);
            if(0 <= nex && nex < 8
                && !(cur == 3 && nex == 4)
                && !(cur == 4 && nex == 3)
                && it == mp.end()){
                que.push(P(tmp, nex));
                mp[tmp] = mp[s] + 1;
            }
        }
    }
}

int main(){
    bfs();
    while(getline(cin, str)){
        str.erase(remove(str.begin(), str.end(), ' '), str.end());
        cout<<mp[str]<<endl;
    }
}