Author: loop3r
Date: 20260504
tag: 广度优先搜索
link: https://www.luogu.com.cn/problem/P1379

题目描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

string s;
int A[3][3];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
unordered_map<string, bool> vis;
unordered_map<string, int> dis;

void to_vec(string s) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            A[i][j] = s[i * 3 + j] - '0';
        }
    }
}

string to_state() {
    string s;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            s += A[i][j] + '0';
        }
    }
    return s;
}

pair<int, int> find() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (A[i][j] == 0) {
                return {i, j};
            }
        }
    }
}

int main() {
    cin >> s;

    queue<string> q;
    q.push(s);
    vis[s] = true;
    dis[s] = 0;

    while (q.size()) {
        string state = q.front();
        q.pop();

        if (state == "123804765") break;

        to_vec(state);
        pair<int, int> pos = find();

        for (int i = 0; i < 4; i++) {
            int nx = pos.first + dx[i];
            int ny = pos.second + dy[i];

            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;

            swap(A[nx][ny], A[pos.first][pos.second]);
            string ns = to_state();
            if (!vis[ns]) {
                q.push(ns);
                vis[ns] = true;
                dis[ns] = dis[state] + 1;
            }
            swap(A[nx][ny], A[pos.first][pos.second]);
        }
    }

    cout << dis["123804765"] << endl;

    return 0;
}