題意#
這題給你一個 3x3 的數字棋盤，上面放著 1 到 9。
每次你可以交換兩個相鄰（上下左右）的數字。
目標是找出最少需要交換幾次。
才能把整個盤面變成由左到右、由上到下，排成 1 2 3 4 5 6 7 8 9 的最終狀態。
思路#
這其實是經典的「八數字推圖遊戲」變形。
看到要求「最少次數」，直覺就是用廣度優先搜尋 (BFS) 來找最短路徑。
我習慣把整個 3x3 的盤面直接壓成一個長度為 9 的字串。
例如 "123456789"。
這樣一來狀態表示變得非常簡單。
同時也方便丟進 unordered_map 來記錄走過的盤面，避免無窮迴圈。
為了加速相鄰元素的交換，我會先把盤面上所有合法的相鄰索引對寫死在一個陣列裡。
接著就是標準的 BFS 流程。
從起始字串開始，每次把字串中相鄰的位置交換產生新狀態。
如果沒看過就加入佇列，直到碰見目標字串為止。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
// 預先建好 3x3 盤面上所有合法的相鄰索引對 (對應一維字串的 0~8 索引)
// 前六對是橫向相鄰，後六對是縱向相鄰
vector<PII> xy = {
{0, 1}, {1, 2}, {3, 4}, {4, 5}, {6, 7}, {7, 8},
{0, 3}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {5, 8}
};
signed main() { WA();
string s; int n;
// 將輸入的 9 個數字串接成一個長度為 9 的字串代表初始狀態
while (cin >> n) s += char(n+'0');
// BFS 用的佇列，存放 {當前盤面字串, 目前步數}
queue<pair<string, int>> q;
// 記錄走過的盤面狀態，避免重複搜尋
unordered_map<string, int> vis;
vis[s] = 1; q.push({s, 0});
int ans = -1;
while (q.size()) {
auto [s, step] = q.front(); q.pop();
// 抵達目標盤面，記錄步數並結束 BFS
if (s == "123456789") {
ans = step;
break;
}
// 嘗試所有合法的相鄰交換
for (auto &[x, y] : xy) {
swap(s[x], s[y]); // 交換產生新盤面
// 如果這個盤面沒見過，就標記已訪問並推入佇列
if (vis.find(s) == vis.end()) vis[s] = 1, q.push({s, step+1});
swap(s[x], s[y]); // 復原，繼續嘗試下一個交換
}
}
cout << ans;
}
