#P4599. [Sdoi2016]墙上的句子
[Sdoi2016]墙上的句子
[SDOI2016] 墙上的句子
题目描述
一面墙被划分成 行 列的格子。每个格子是空白,或写有一个大写英文字母。每一行或列中,相邻空白或边界之间的极长连续字母段构成一个单词。行可从左往右或从右往左读,列可从上往下或从下往上读。每行或列的所有单词采用该行或列的同一阅读方向。
保证每一行或列独立地满足以下一种情况:其中每个单词的字典序都不大于自身反转后的字典序,或都不小于自身反转后的字典序。各行列可以满足不同的情况。
有些行列的阅读方向已知,其余可以任选。确定所有阅读方向后,将全部读出的不同单词收录为字典。求字典中反转后仍在字典中的单词种数的最小值。若一对互为反转的不同单词均被收录,两种都计入。任意被收录的回文单词计一次。
输入格式
第一行一个整数 ,表示测试组数。每组测试依次给出:
- 两个整数 ,表示行数和列数。
- 个整数,依次给出各行的方向。 表示从左往右, 表示从右往左, 表示方向未知。
- 个整数,依次给出各列的方向。 表示从上往下, 表示从下往上, 表示方向未知。
- 行,每行一个长度为 的字符串,只包含大写英文字母和下划线。下划线表示空白格。
输出格式
输出 行,每组输出可以得到的最小单词种数。
1
2 10
0 0
0 0 0 0 0 0 0 0 0 0
ADA_JARVIS
ADA_SIVRAJ
3
数据范围
,。