【Aizu - 0121】Seven Puzzle （反向bfs）

-->Seven Puzzle

原文是日语 这里就直接写中文了

 Descriptions:

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 6，图(c)为2 7 3 4 0 5 1 6。

input

以上格式提供多个谜题。请处理到输入的最后。给定的谜题的数量在1,000以下。

output

请将每个拼图输出到最后一行的最小麻烦。

Sample Input

Output for the Sample Input

题目链接：
https://vjudge.net/problem/Aizu-0121

从目标卡牌序列"01234567"开始着手入队列，然后走出不同的卡牌序列，再将走出这些卡牌序列的步数存储，最后比对题目要求的卡牌序列，找出答案即可，代码有详解

AC代码：

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 310
using namespace std;
map<string,int>mp;//卡牌序列对应的步数
queue<string>q;//卡牌序列
string now,net;
string s;
//移动方向，右，左，上，下（给定一维数组，要向上（下），就是往前（后）推四张牌）
int dt[]= {1,-1,4,-4};
void bfs()
{
    q.push("01234567");
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        int pos=now.find('0');//找到0的位置
        for(int i=0; i<4; i++)
        {
            int tpos=pos+dt[i];
            //3、7位置不能往右移   0、4位置不能往左移
            if(tpos>=0&&tpos<8&&(!((pos==3||pos==7)&&i==0)&&!((pos==0||pos==4)&&i==1)))
            {
                net=now;
                swap(net[pos],net[tpos]);//交换pos和tpos位置的数字，形成新的卡牌序列
                if(mp[net]==0)//卡牌序列没出现过
                {
                    mp[net]=mp[now]+1;//步数+1
                    q.push(net);
                }
            }
        }
    }
    return;
}
int main()
{
    bfs();//初始化，找出所有可能的卡牌序列
    mp["01234567"] = 0;
    while(1)
    {
        s="";//存放题目要求的卡牌序列
        int a = 8,b;
        while(a--)
        {
            if(!(cin >> b))
                return 0;//这一行的处理是加了个结尾，不加的话死循环
            s += b+'/0';
        }
        cout <<mp[s] << endl;
    }
    return 0;
}