[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 long

int 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;
}

​

原文地址：https://blog.csdn.net/zeisenphael/article/details/145170564

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！