卡片換位

原題目鏈接

題目描述

你玩過華容道的游戲嗎？

這是一個類似的，但更簡單的游戲。

看下面的 3 × 2 格子：

+---+---+---+
| A | * | * |
+---+---+---+
| B |   | * |
+---+---+---+

在其中放置了 5 張牌，其中：

• A 表示關羽，
• B 表示張飛，
• * 表示士兵，
• 空格表示空位。

你可以將一張牌移動到相鄰的空格中（對角線不算相鄰）。

游戲目標是：讓關羽和張飛交換位置，其他牌的位置可以隨意。

---

輸入描述

輸入兩行，每行包含 3 個字符，表示當前局面。

字符說明：

• A：關羽
• B：張飛
• *：士兵
• （空格）：空位

---

輸出描述

輸出一個整數，表示最少多少步可以完成關羽與張飛的位置交換。

---

輸入輸出樣例

示例

輸入

* A
**B

輸出

17

---

（注：要求最少移動步數達成目標，其他牌隨意。）

c++代碼

#include<bits/stdc++.h>using namespace std;string a, b;
int l_A, l_B;
unordered_set<string> mp;class solution{
public:int k, l_A, l_B;long long ans;solution() { this->ans = 0; }
};long long bfs() {vector<vector<int>> arr = { {1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {3, 5, 1}, {4, 2} };string c = a + b;solution s, mid;for (int i = 0; i < 6; i++) {if (c[i] == ' ') s.k = i;else if (c[i] == 'A') l_A = i, s.l_A = i;else if (c[i] == 'B') l_B = i, s.l_B = i;}queue<solution> qu;qu.push(s);while(!qu.empty()) {s = qu.front(), qu.pop();string temp = to_string(s.k) + " " + to_string(s.l_A) + " " + to_string(s.l_B);if (mp.find(temp) != mp.end()) continue;mp.insert(temp);if (s.l_A == l_B && s.l_B == l_A) return s.ans;for (int x : arr[s.k]) {mid = s;mid.k = x, mid.ans++;if (mid.l_A == x) mid.l_A = s.k;if (mid.l_B == x) mid.l_B = s.k;qu.push(mid);}}return -1;
}int main() {getline(cin, a);getline(cin, b);cout << bfs();return 0;
}//by wqs

題目解析

純純暴力BFS題目