Xiao Jia is experimenting. She wants to combine 4 types of chemical reagents, "A, B, C, D," with "1, 2, 3, 4" types of chemical powders to observe the chemical reactions after fusion. However, each of these chemical reagents must not be combined with specific powders, or else an explosion will occur.
Please write a program to help Xiao Jia complete the task. When there is more than one fusion method, please output all possible fusion methods (powders will not be reused), if unable to find a fusion method that meets the requirements, print "No".
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line consists of a positive integer N (1 ≤ N ≤ 10), indicating the number of test cases. Each test case consists of 4 lines. The first character of each line is a single English letter (A, B, C, D) representing a chemical reagent, followed by the numbers (1, 2, 3, 4) representing the powders that cannot be added, separated by spaces, and ending with 0. If there are no powders that cannot be added, simply end the line with 0. | For each test case, first output ABCD, followed by the powders to be fused. Output each fusion method (without repeating powders) on a separate line, in ascending order based on the combination of the 4 numbers. If unable to find a fusion method that meets the requirements, print "No". Print an empty line at the end of each test case. Each output line ends with a newline character. |
| 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 |
Thought Process
When receiving the types of powders that cannot be added, you can declare a Vector<Map to store the numbers of powders that cannot be added for each chemical (A to D) in a Map and push it back to the Vector.
Next, we need to run DFS. The parameters will require a Vector medicine, representing the current sorting order, and a Map, indicating which powders have been used because they cannot be reused. First, check if medicine.size() == 4, which means powders A to D have been sorted. If so, output the data in medicine. Otherwise, continue sorting.
Run a for loop from 1 to 4, representing the number of the powder to be added. Inside the for loop, declare a variable index = medicine.size(), which represents the position of the powder we are currently sorting. If the current powder number has not been used and is not a dangerous powder in this position (according to the given constraints), update the Map to mark this powder as used, push this powder number into medicine, and call DFS again.
After the call, remember to restore the changes made to the Map and medicine.
Certainly! We can set a boolean variable ok to false initially. If a valid permutation is found during DFS, we'll set it to true. After running all DFS calls, if !ok, it means there are no valid permutation combinations available, so we output "No".
Sample Code－ITSA 202405 #2: Fusing Experiment
#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