小佳在做實驗。她想將 4 種化學藥劑「A、B、C、D」中，加入「1、2、3、4」種化學粉末，以觀察融合後的化學反應。但這些化學藥劑中，各別有絕對不能加入的粉末，否則會發生爆炸。
請你寫一個程式來協助小佳完成工作。當融合方式不只一組時，請輸出所有可能的融合方式 (粉未不會重覆使用），若無法找出一種符合要求的融合方式，則印比「No」。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行為一個正整數 N (1 ≤ N ≤ 10），表示共有 N 筆測試資料。 每筆測試資料有 4 行，每行第一個字元為 1 個英文字母 (A、B、C、D) 表示化學藥劑，後面接著不能加入的粉未數字 (1、2、3、4），以空格格開，最後以 0 做為結尾。 若沒有不能加入的化學粉末，則直接以 0 結尾。 | 每組測試資料先輸出 ABCD，換行後再輸出要融合的粉末，每一種融合方式 (粉未不會重覆使用) 輸出一行 (依照4個號碼所組成的數字以遞增順序印出），若無法找出一種符合要求的融合方式，則印出「No」。 每組測試資料最後都需印一行空行。每行輸出最後都有換行符號。 |
| 3 A 1 3 0 B 2 4 0 C 2 3 0 D 2 3 0 A 1 2 4 0 B 2 4 0 C 2 3 0 D 4 0 A 1 2 0 B 2 4 0 C 2 3 0 D 2 0 | ABCD 2314 2341 ABCD 3142 No |
解題思路
在收不能放入的粉末種類時，可以宣告一個 Vector<Map<int, int>，將 A 到 D 不能放入的粉末數字存到一個 Map 中並 Push_Back 到 Vector 裡。
再來就是跑 DFS，參數會需要一個 Vector<int> medicine，代表目前的排序方式是什麼，還有一個 Map<int, int>，代表哪些粉末已經使用過了，因為不能重複使用。先判斷如果 medicine.size() == 4 代表 A 到 D 的粉末都已經排好了，就將 medicine 中的資料做輸出，否則就繼續排序，跑一個 For迴圈 從 1 到 4，代表要放入的粉末數字，在 For迴圈 中可以宣告一個變數 index = medicine.size()，這個 index 就代表我們目前要排第幾個位置的粉末。如果目前跑到的粉末數字沒有被用過且不是 index 這個位置的危險粉末，就將 Map 中的資料更新已經用過這個粉末了，並且將這個粉末數字 Push_Back 到 medicine 中，然後再次呼叫 DFS。呼叫完之後記得要將剛剛更動過了 Map 還有 medicine 做還原。
可以預設一個布林值 ok = false，如果有計算出排列順序的話就將其設為 true，在跑完所有 DFS 之後，如果 !ok 代表沒有可以使用的排列組合，就輸出「No」。
範例程式碼－ITSA 202405 #2：融合實驗
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<map<int, int>>v;
bool ok = false;
void DFS(vector<int>medicine, map<int, int>MAP) {
if (medicine.size() == 4) {
if (!ok) cout << "ABCD\n";
for (int i = 0; i<4; i++) cout << medicine[i];
cout << "\n";
ok = true;
return;
}
for (int i = 1; i<=4; i++) {
int index = medicine.size();
if (MAP[i] == 0 && v[index][i] == 0) {
MAP[i]++;
medicine.push_back(i);
DFS(medicine, MAP);
medicine.pop_back();
MAP[i]--;
}
}
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++) {
v.clear();
ok = false;
for (int j = 0; j<4; j++) {
char ch;
cin >> ch;
int tmp;
map<int, int>MAP;
while (cin >> tmp && tmp != 0) MAP[tmp]++;
v.push_back(MAP);
}
vector<int>medicine;
map<int, int>MAP;
DFS(medicine, MAP);
if (!ok) cout << "No\n";
cout << "\n";
}
}
//ITSA 202405 #2
//Dr. SeanXD