【每日一题】Problem 653B. Bear and Compressing

原题

解决思路

根据当前字符串的首字符进行深度递归即可

误区

字符串是从头开始匹配的，因此只需要对首字符进行替换

#include <bits/stdc++.h>

int dfs(std::map<char, std::vector<std::string>> &r,
         char c, int n, int target)
{
    if (n == target) {
        return 1;
    }

    int ans = 0;
    for (auto &p: r[c]) {
        ans += dfs(r, p[0], n + 1, target);
    }
	
    return ans;
}

int main()
{
    int n, q;
    std::cin >> n >> q;
    std::map<char, std::vector<std::string>> r;
    while (q--) {
        std::string a;
        char b;
        std::cin >> a >> b;
        r[b].push_back(a);
    }

    std::map<std::string, bool> d;
    std::cout << dfs(r, 'a', 1, n) << "\n";

    return 0;
}