AOJ 0121 Seven Puzzle

原题目如下：

7拼图

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

解题思路：

这道题是一个反向bfs的题目，我们可以将最终目标的拼图01234567，将其中的0拼图移动位置，列举出所有的情况，放置在表中。最后，将输入的序列进行查表得出最小步数。并且，这道题适合用字符串来存储拼图，而不适合用数组。用数组反而会更加麻烦。并且当移动拼图时，一定要注意0拼图的位置。当0拼图在0位置或4位置时不能向左移，0拼图在3位置或7位置不能向右移。如果知道了这些这道题就可以迎刃而解了。(逆向思维真的很重要！)

代码如下：

#include <iostream>
#include <cstdio>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
queue<string> Q;                         //声明一个用于存放拼图的队列
map<string, int> Graph;                 //代表某拼图和从原拼图构成这个拼图步数的对应关系
string temp, now;                      //temp代表当前遍历的拼图，now代表当前遍历的拼图移动后生成的新拼图
int direction[4]={4,-4,-1,1};         //声明一个方向数组，这个数组代表0拼图的上下和左右移动
void bfs();                          //代表进行广度优先搜索的函数

void bfs()                          //代表将原拼图进行移动，通过bfs穷举出移动后拼图的所有状况，将其储存在Graph中
{
	int i;
	Q.push("01234567");         //将原拼图进行入队
	while (!Q.empty())
	{
		temp = Q.front();
		Q.pop();
		int pos = temp.find(‘0‘);      //找出0拼图在字符串中的位置，根据题意，我们需要根据0拼图进行移动
		for (i = 0; i < 4; i++)
		{
			int movepos = pos + direction[i];    //代表0地图（上下左右移动之后的位置）
			if (movepos >= 0 && movepos < 8 && (!((pos == 0 || pos == 4) && i == 2) && !((pos == 3 || pos == 7) && i == 3)))     //如果0地图移动之后的范围在拼图之内，并且0拼图在0位置或4位置时不能向左移，0拼图在3位置或7位置时不能向右移
			{
				now = temp;
				swap(now[pos], now[movepos]);    //将0拼图和0拼图所移动的方向进行交换
				if(Graph[now] == 0)              //如果交换过的拼图状态在Graph中还没有出现过
				{ 
					Graph[now] = Graph[temp] + 1;//将当前移动后的拼图的移动次数修改为当前遍历的地图的移动次数+1，代表当前移动后的拼图是由当前正在遍历的拼图移动一次变成的。
					Q.push(now);                 //将新拼图进行入队
				}

			}
		}
	}
	return;

}

int main()
{
	bfs();
	Graph["01234567"] = 0;     //原拼图需要0步数就可以构成原拼图
	while (true)
	{
		int count = 8;             //代表输入的计数变量（要输入8个拼图)
		int b;                     //代表要输入的单个拼图
		string s = "";             //代表要输入的8个拼图，用变量s来表示
		while (count--)
		{
			if (!(cin >> b))       //在测试平台中测试完毕之后会有一个结束标志EOF，所以当测试平台输入EOF时，这个函数就直接退出，从而避免死循环
			{
				return 0;
			}
			s += b + ‘0‘;
		}
		cout << Graph[s] << endl;
	}

}

AOJ 0121 Seven Puzzle

原文：https://www.cnblogs.com/gao79135/p/14027323.html