怀旧书本
#include <bits/stdc++.h>
using namespace std;
void bfs() {}
int main() {
    string start;
    char c;
    for (int i = 0; i < 9; ++i) {
        cin >> c;
        start.push_back(c);
    } 
    
    queue<string> q;
    unordered_map<string, int> d;
    string end = "12345678x";
    q.push(start);
    d[start] = 0;
    int da[5] = {0, 1, 0, -1, 0};
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        
        int p = cur.find('x');
        int r = p / 3, c = p % 3;
        for (int i = 0; i < 4; ++i) {
            int nr = r + da[i], nc = c + da[i + 1];
            if (nr < 0 || nr >= 3 || nc < 0 || nc >= 3) continue;
            int np = nr * 3 + nc;
            auto nstate = cur;
            swap(nstate[np], nstate[p]);
            if (nstate == end) {
                cout << d[cur] + 1 << endl;
                return 0;
            }
            if (d[nstate]) continue;
            d[nstate] = d[cur] + 1;
            q.push(nstate);
        }
        
    }
    
    cout << -1 << endl;
    
    return 0;
}
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/eight-digital-bfs/
最后修改日期:2020年5月8日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。