挑战程序设计竞赛 2章习题 AOJ 0121 Seven Puzzle bfs

地址  https://vjudge.net/problem/Aizu-0121

题目大意是 0~7 8个数字随机分布在两行中，我们可以上下左右交换0和它周边的数字来将8个数字组成最终形态

如图

最终形态

输入格式

一行输入0~7   8个数字  空格隔开

输出格式

每行输出上述数据 达到最终形态的步数

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得到最短移动步骤

但是由于没有明确的移动目标，我们不清楚如何移动才是与最终形态接近了，所以可以逆向思考，从最终形态生成所有可能的组合和达到这个组合的步数，使用哈希记录方便查询。

之后直接查询即可。

进阶的资料 随着状态数目的增加比如八数码 需要考虑状态压缩。 一个状态是否可以达到最终形态，可以使用逆序对来确认，关键字是康托展开，大家可以自行查询。

代码

// 11235555.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

string targetStr = "01234567";

unordered_map<string, int> mm;

int mv[4] = { 1,-1,4,-4 };

void bfs() {
    queue<pair<string, int>> q;
    q.push({ targetStr ,0 });

    while (!q.empty()) {
        pair<string, int> p = q.front(); q.pop();
        string  s = p.first; int step = p.second;
        mm[s] = step;

        int idx = s.find('0');
        for (int i = 0; i < 2; i++) {
            int newidx = idx + mv[i];
            if (idx / 4 == newidx / 4 && newidx >=0 && newidx<8) {
                string tmp = s;  swap(tmp[idx], tmp[newidx]);
                if (mm.count(tmp) == 0) {
                    mm[tmp] = step + 1;
                    q.push({ tmp,step + 1 });
                }
            }
        }
        for (int i = 2; i < 4; i++) {
            int newidx = idx + mv[i];
            if (idx / 4 != newidx / 4 && newidx >= 0 && newidx < 8) {
                string tmp = s;  swap(tmp[idx], tmp[newidx]);
                if (mm.count(tmp) == 0) {
                    mm[tmp] = step + 1;
                    q.push({ tmp,step + 1 });
                }
            }
        }
    }



}

int main()
{
    bfs();
    string s;
    while (getline(cin,s)) {
        string curr;
        for (auto& e : s) {
            if (e != ' ') curr += e;
        }
        cout << mm[curr] <<endl;
    }

    return 0;
}