7拼图
7数码问题。在2*4的棋盘上，摆有7个棋子，每个棋子上标有1到7的某一个数字，不同棋子上的数字不相同。棋盘还有一个空格，与空格相邻(上下左右)的棋子可以移动到空格中，该棋子原先位置成为空格。给出一个初始状态(保证可以转移到最终状态)，找出一种从初始状态转变到给定最终状态的移动棋子最小的步数。
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)，那么反过来只要记录最终状态到所有结果的最小步数，接下来查表即可。
从目标卡牌序列"01234567"开始着手，使用BFS，记录到达不同序列状态的最小步数，最后比对题目要求的序列状态，找出答案
和一般的bfs不同，这题的bfs没有明确的移动对象，看似任意一个数都可以当成对象移动。但是其他格子只能与格子0交换，我们便将格子0作为移动的对象。
用map<string,int>表示(“01234567”)到string的最小步数int，只要当前结果还未记录，就加入map，直到穷尽所有状态。
四个方向对应的位置变化为:
int mynext[4] = { 1,-1,4,-4 };
需要注意有些位置不能向某些方向移动(例如左下角不能减1，右上角不能加一)。
AC代码
#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
map<string, int> map1;
int mynext[4] = {
1,-1,4,-4 };//位置变化
void BFS() {
queue<string> que;string s1 = "01234567";que.push(s1);map1[s1] = 0;while (!que.empty()) {
string now = que.front();que.pop();//t是字符串中‘0’的位置int t;for (int i = 0; i < now.size(); i++) {
if (now[i] == '0') {
t = i;break;}}for (int i = 0; i < 4; i++) {
int nt = t + mynext[i];if (nt < 0 || nt>7 ||(t==3&&nt==4)||(t==4&&nt==3)) continue;//提前剪枝string next = now;swap(next[t], next[nt]);if (map1.find(next) == map1.end()) {
//尚未搜索到的状态map1[next] = map1[now] + 1;que.push(next);}}}
}
int main() {
BFS();//cout << map1.size();//20160string s;//getline(cin, s) cin>>s 无法吃空格while (getline(cin, s)) {
//消去空格int t = s.find(' ', 0);while (t != string::npos) {
s.erase(t, 1);t = s.find(' ', t);}cout << map1[s] << endl;}return 0;
}