一道比较普通的字符串题
与之前的一道题字串变换类似
传送门：字串变换。
大意 ：给定一些替换规则，可以使特定的两个字符变为一个特定字符，问使其变化为一个 单字符 'a' 的方案数有几个。
思路 ：由于 n 的范围很小，可以考虑生成 n 的所有排列情况，再进行判断 & 搜索。
搜索的策略也比较简单，由于 提议限制为特定的两个字符 变换为 一个字符，所以可以直接打出这种情况。注意回溯时 要先把 要替换的字符取出，替换上可替换的字符，判断是否符合要求， 若不符合，则再把取出的字符放回去。
#include <iostream> #include <cstdio> #define Max 30 using namespace std; char merge_from [Max][Max]; char merge_to [Max][Max]; char merge [Max]; int N, Q; int Answer ; bool judge (int X) { if (X == N && merge [X] == 'a') return true; // 如果串的长度已经到了给定的长度，且最后一个字符为a，则证明该串是符合要求的 for (int i = 1; i <= Q; i++) { if (merge [X] == merge_from [i][1] && merge [X + 1] == merge_from[i][2]) //如果当前串的当前字符符合第i个可缩合的规则 { char just = merge [X + 1]; //取出待替换的字符，准备若替换后不成功的话再放回去 merge [X + 1] = merge_to [i][1]; //替换 bool flag = judge (X + 1); //判断接下来的字符 merge [X + 1] = just; // 把 取出的字符再放回去 if (flag == true) return true; // 如果该串符合要求，则返回一个true } } } void DFS (int X) { if (X == N + 1) { if(judge (1) == true) // 从当前生成的串的第一个字符开始判断 Answer++; //如果 符合要求 答案加1 return; //返回 } for (int i = 0; i <= 5; i++) // 枚举每一种 串的排列方式 { merge [X] = i + 'a'; DFS (X + 1); } } int main() { ios :: sync_with_stdio (false); scanf ("%d%d", &N, &Q); for (int i = 1; i <= Q; i++) { scanf ("%s", merge_from [i] + 1); // 读入 缩合规则 + 1 的目的是使字符串从下标为1开始存 scanf ("%s", merge_to [i] + 1); // 读入 缩合后的氨基酸 } DFS (1); // 从第一种串的情况开始搜索 printf ("%d", Answer ); return 0; }