AOJ 0121 Seven Puzzle {广度优先搜索}(*)

简介:

原题

这里写图片描述

这里写图片描述

这里写图片描述

题意

题意是有一个输入,比如:

1 0 2 3 4 5 6 7

摆成如下形状:

1 0 2 3
4 5 6 7

0表示空格,其他数字可以移动到0的位置。最后需要到如下形状:

0 1 2 3
4 5 6 7

上面的这种情况是需要移动一步,也就是0和1直接移动就好。

代码

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

int dx[4] = { 1,-1,4,-4 };
map<string, int>res;

void solve(void) {
    queue<string>que;
    que.push("01234567");
    while (!que.empty()) {
        string v = que.front();
        que.pop();
        int pos = 0;
        for (int i = 0; i < 8; i++)
            if (v[i] == '0')pos = i;

        for (int i = 0; i < 4; i++) {
            if (0 <= pos + dx[i] && pos + dx[i] < 8 &&
                !(pos == 3 && i == 0) && !(pos == 4 && i == 1)) {
                string u = v;
                swap(u[pos], u[pos + dx[i]]);

                if (res[u] == 0) {
                    que.push(u);
                    res[u] = res[v] + 1;
                }
            }
        }
    }
}

int main(void) {
    int in;
    res["01234567"] = 1;
    solve();
    while (true) {
        string s;
        for (int i = 0; i < 8; i++) {
            if (!(cin >> in))return 0;
            s += in + '0';
        }
        cout << res[s] - 1 << endl;
    }
    return 0;
}
目录
相关文章
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
AtCoder Beginner Contest 216 G - 01Sequence (并查集 贪心 树状数组 差分约束)
152 0
AtCoder Beginner Contest 216 D - Pair of Balls (思维建图 拓扑排序判断有向图是否有环)
AtCoder Beginner Contest 216 D - Pair of Balls (思维建图 拓扑排序判断有向图是否有环)
125 0
|
测试技术
HDU-1026,Ignatius and the Princess I(BFS+打印路径)
HDU-1026,Ignatius and the Princess I(BFS+打印路径)
HDOJ/HDU 1372 Knight Moves(经典BFS)
HDOJ/HDU 1372 Knight Moves(经典BFS)
134 0
|
C语言
HDOJ/HDU Tempter of the Bone(深搜+奇偶性剪枝)
HDOJ/HDU Tempter of the Bone(深搜+奇偶性剪枝)
98 0