P4487.第1题-字符替换

1000ms

Difficulty: 5

所属公司 : 京东

算法与标签>BFS

题目内容

小明热表于研究字符替换。他拥有一张字符替换表，表上的每一条替换规则形如:将字符串串首的三个连续字符用某个单字符替换。一张替换表示例如下:

$\begin{array}{|c|c|c|} \hline \text { 规则编号 } & \text { 替换前 } & \text { 替换后 } \\ \hline 1 & a b d & e \\ \hline 2 & b c d & e \\ \hline 3 & a b a & b \\ \hline 4 & a b a & a \\ \hline \end{array}$

利用这张替换表，我们就可以对一个字符串进行字符替换了。例如，对于字符串 $ababacd$ 就可以通过如下操作替换成 $e$ 。

一天，小明利用他新研究出的字符替换表将一个长为 $n$ 的字符串 $S$ 替换成了一个单字符 $x$ 在那之后，他睡了一觉，等到醒来的时候， $S$ 竟然遗失了。

小明想知道，在已知字符替换表和单字符 $x$ 的情况下， $S$ 有多少种不同的可能?

输入描述

第一行两个正整数 $n,m$ ,分别表示 $S$ 的长度和字符替换表中的规则数量。保证 $n$ 为奇数。

接下来 $m$ 行，每一行两个字符串 $U,V$ ,表示一条替换规则( $U$ 替换成 $V$ ).保证 $U$ 长度为 $3$ ， $V$ 长度为 $1$ 。保证不会有完全相同的两条替换规则(即不存在 $i,j(i≠j)$ 同时满足 $U_i=U_j$ 和 $V_i=V_j$ ).

接下来一行一个字符 $x$ ,表示经过替换最终得到的单字符。

对于本题中出现的所有字符/字符串(包括 $U，V,x$ )，保证它们仅由小写英文字母组成。

$1≤n≤ 13,1 ≤ m ≤ 15$ ,且 $n$ 为奇数。

输出描述

输出行一个整数，表示替换前的 $S$ 有多少种不同的可能。

样例1

输入

5 5
acd b
acf b
bcc c
bdd e
ccc e
e

输出

说明

三种可能的 $S$ 分别为 $add, acfdd$ , 和 $bccc$ 可以证明没有其它满足条件的 $S$

样例2

输入

9 4
abc d
def g
ghi j
jkl m
m

输出

说明

唯一可能的 $S$ 是 $abcefhiki$ .

输入

预期输出（选填）

解题思路

P4487.第1题-字符替换

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About