51°

【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

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

Output for the Sample Input

0
1
28

题目链接:
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;
}

 

原文链接:https://www.cnblogs.com/sky-stars/p/11185653.html

全部评论: 0

    我有话说: