POJ1077:Eight

Question

描述
The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x

where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->

The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
输入
You will receive a description of a configuration of the 8 puzzle. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3
x 4 6
7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8
输出
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line.
样例输入
2 3 4 1 5 x 7 6 8
样例输出
ullddrurdllurdruldr
来源
South Central USA 1998

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cstring>
#include <cstdlib>
using namespace std;//一共9！状态，012345678
struct status {
    char a[9];
    vector<char> path;
};
queue<status> q;
set<int> st;//vis[]
void newStatus(status last, int otherpos, int zeropos, char c)
{
    if (otherpos >= 0 && otherpos <= 8) {
        swap(last.a[otherpos], last.a[zeropos]);
        status newS;
        if (st.find(atoi(last.a)) == st.end()) {
            newS = last;
            newS.path.push_back(c);//路径
            q.push(newS);//入队
            st.insert(atoi(last.a));//vis
        }
    }
}
int main()
{
    status initialStatus;
    char Input[50];
    initialStatus.path.clear();
    while (cin.getline(Input, 48)) {
        bool flag = false;
        int j = 0;
        for (int i = 0; Input[i]; i++)
            if (Input[i] != ' ')
                if (Input[i] == 'x')
                    initialStatus.a[j++] = '0';
                else
                    initialStatus.a[j++] = Input[i];
        st.clear();
        while (q.size() != 0)
            q.pop();
        q.push(initialStatus);
        st.insert(atoi(initialStatus.a));
        while (q.size() != 0) {
            status tmp;
            tmp = q.front();
            if (atoi(tmp.a) == 123456780) {
                for (int i = 0; i < tmp.path.size(); i++)
                    cout << tmp.path[i];
                cout << endl;
                flag = true;
                break;
            }
            q.pop();
            int zeropos;
            for (int i = 0; i < 9; i++)
                if (tmp.a[i] == '0')
                    zeropos = i;
            newStatus(tmp, zeropos - 3, zeropos, 'u');
            newStatus(tmp, zeropos + 3, zeropos, 'd');
            if (zeropos % 3 != 0)
                newStatus(tmp, zeropos - 1, zeropos, 'l');
            if (zeropos % 3 != 2)
                newStatus(tmp, zeropos + 1, zeropos, 'r');
        }
        if (flag == false)
            cout << "unsolvable" << endl;
    }
}

过不了，为什么，感觉没问题，试了几个测试用例跟网上通过了的答案都一样，路径这样记录有啥问题吗。

Answer 1

代码没有问题，是超时了。这个题用A*算法可以过。下面是我以前的代码，欢迎交流

/**
 * @Information: Created by zdw on 2020-02-16 18:26:32.
 * @Description: A*搜索的例题
 * 估价函数的设计:
 * 即使每一步都是有意义的,从任何一个状态到目标状态的移动步数也不可能小于所有数字当前位置与目标位置的曼哈顿距离之和
 * 
 *
 * https://www.acwing.com/problem/content/description/180/
 */
#include <iostream>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, string> PIS;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char op[] = {'u', 'r', 'd', 'l'};

//计算出这个状态到最后的状态的曼哈顿距离
int f(string state) {
    int res = 0;
    for (int i = 0; i < 9; ++i) {
        if (state[i] != 'x') {
            int t = state[i] - '1';//t代表i应该放的位置，而不是i的值
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    }
    return res;
}

string bfs(string start) {
    string state = start, end = "12345678x";

    unordered_map<string, pair<string, char >> prev;//分别存当前状态，上一个状态以及操作；可通过当前状态返回到上一个状态
    unordered_map<string, bool> st;
    unordered_map<string, int> dist;

    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
    heap.push({f(state), state});//A*算法，当前的状态预估距离和当前状态入队
    dist[state] = 0;

    while (heap.size()) {
        PIS tp = heap.top();
        heap.pop();

        state = tp.second;//取出状态进行更新

        if (state == end) //等于目标状态直接退出
            break;

        if (st[state])//由于是最小的，每个状态只能访问一次
            continue;
        st[state] = true;

        //找到空格的位置;
        int x, y;
        for (int i = 0; i < 9; ++i) {
            if (state[i] == 'x') {
                x = i / 3, y = i % 3;
                break;
            }
        }

        string raw = state;//储存好原状态

        //枚举四个方向
        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                state = raw;

                //与空格进行交换，形成新的状态
                swap(state[x * 3 + y], state[a * 3 + b]);

                //如果这个状态没有出现或者出现过但是太大了(大于了由这一步转换而来值)，就更新
                if (!dist.count(state) || dist[state] > dist[raw] + 1) {
                    dist[state] = dist[raw] + 1;
                    prev[state] = {raw, op[i]};//记录上一个操作
                    heap.push({f(state) + dist[state], state});
                }

            }
        }
    }
    //从最后开始回溯答案，最后反转一下

    string ans = "";
    while (state != start) {
        ans += prev[state].second;//取出操作
        state = prev[state].first;//移动到上一个状态去
    }
    reverse(ans.begin(), ans.end());

    return ans;
}

int main() {
    string g, s;
    char c;
    while (cin >> c) {
        g += c;
        if (c != 'x')s += c;
    }
    //获取逆序对数
    int cnt = 0;
    for (int i = 0; i < 8; ++i) {
        for (int j = i + 1; j < 8; ++j) {
            if (s[i] > s[j])
                cnt++;
        }
    }
    //如果逆序对为偶数，则无解
    if (cnt & 1)
        puts("unsolvable");
    else
        cout << bfs(g) << endl;
    return 0;
}