[PAT 甲级] 1179 Chemical Equation （DFS）

英文题目

题目翻译（GPT）：

1179 化学方程式

化学方程式是一种用符号和公式表示化学反应的方法，其中反应物在方程式的左侧，生成物在右侧。例如：
CH₄ + 2O₂ -> CO₂ + 2H₂O
表示反应物为甲烷和氧气（CH₄ 和 O₂），生成物为二氧化碳和水（CO₂ 和 H₂O）。

现在给定一组反应物和生成物，你需要判断通过何种方式可以得到这些生成物，要求每种反应物只能使用一次。为简化起见，我们假设方程式右侧的所有物质都作为单一生成物。

输入说明

输入文件包含一个测试用例。对于每个测试用例：

第一行给出一个整数 N （2 ≤ N ≤ 20），表示 N 个反应物的索引，它们是 2 位数字的不同索引。
第二行给出一个整数 M （1 ≤ M ≤ 10），表示 M 个生成物的索引，它们也是 2 位数字的不同索引。
接下来是一正整数 K （K ≤ 50），表示接下来的 K 行反应方程。

每行以如下格式表示反应方程：

reactant_1 + reactant_2 + ... + reactant_n -> product

其中，所有反应物是不同的，并且按照索引递增排序。

注意

确保同一组反应物不会生成两个或更多不同的生成物。例如：
01 + 02 -> 03 和 01 + 02 -> 04 是不可能的。
如果某个反应物未参与反应，则不能仅以它自身生成生成物。例如：
01 -> 01 是不允许的，无论该方程是否在输入中。
每种生成物在反应方程列表中不会有超过 5 种不同的生成方式。

输出说明

对于每个测试用例，输出使用给定反应物得到所有指定生成物的方程式。注意，每种反应物只能被使用一次。

每个方程占一行，格式与输入中的方程一致，且生成物的顺序与输入中的顺序相同。
对于每个生成物，如果存在多个解决方案，输出字典序最小的方案（按照反应物序列递增的顺序比较）。
- 例如，反应物序列 {a₁, …, aₘ} 被认为比序列 {b₁, …, bₙ} 小，当且仅当存在一个最小下标 j，使得 aⱼ < bⱼ，且前 j-1 项相等。

保证至少存在一个解决方案。

思路：

看到N和M的范围就注定了这题是暴搜加回溯，至于字典序，直接对于方程式的字符串排序就行，要能熟练运用 map 以及 string 的话，这题就很简单了。

代码

#include<bits/stdc++.h>using namespace std;const int N = 110;#define int long longint n, m, k;bool ans = 0;string a[N];
map<string, int> reac, pro;
map<string, vector<string>> equ;
map<string, string> ways;void dfs(int u) 
{if(u == m + 1) {for (int i = 1; i <= m; i++) {string p = a[i];string e = ways[p];cout << e.substr(0, 2);for (int j = 2; j < e.size(); j+=2) {cout << " + " << e.substr(j,2);}cout << " -> " << p << endl;}ans = 1;return ;}string p = a[u];for (string e : equ[p]) {int f = 1;for (int i = 0; i < e.size(); i+=2) {string r = e.substr(i, 2);if(reac[r] == 0) {f = 0;break;}}if(!f) continue;for (int i = 0; i < e.size(); i+=2) {string r = e.substr(i, 2);reac[r] = 0;}ways[p] = e;dfs(u + 1);if(ans) return;for (int i = 0; i < e.size(); i+=2) {string r = e.substr(i, 2);reac[r] = 1;}ways[p] = "";}
}void solve()
{cin >> n;for (int i = 1; i <= n; i++) {string s;cin >> s;reac[s] = 1;}cin >> m;for (int i = 1; i <= m; i++) {cin >> a[i];string p = a[i];if (reac[p] == 1 && equ[p].size() == 0) {equ[p].push_back(p);}}cin >> k;getchar();while(k --) {string s;getline(cin, s);string p = s.substr(s.size() - 2), h;for (int i = 0; i < s.size() - 6; i += 5) {h += s.substr(i, 2);}equ[p].push_back(h);}for (auto& it : equ) {sort(it.second.begin(), it.second.end());}dfs(1);return ;
}signed main()
{int T = 1;while(T--) solve();return 0;
}