/ Vijos / 题库 /

墙上的句子

墙上的句子

描述

  考古学家发现了一堵写有未知语言的白色的墙壁。上面有一个N行M列的格子,其中有些格子内被填入了某个A至Z的大写字母,还有一些格子留作空白什么也没有填入。已知横着或竖着的连续若干个字母会形成一个单词,且每一行的阅读顺序有可能是从左往右或从右往左,每一列的阅读顺序也有可能是从上往下或从下往上。也就是说对于一行来说,从左往右可以被看作是若干个单词形成的句子,相邻两个单词被一个或多个空白格子分割开来;也有可能是从右往左被看作是一个句子。竖直方向也有相似的情形。
  遗憾的是,我们并不完全知道每一行每一列应该有的阅读顺序(从左向右还是从右向左,从上向下还是从下向上)。但是可以猜测,有些单词S会满足翻转过来亦然是一个单词。例如对于英文单词BOY来说,翻转过来YOB也是一个英文单词。
  此外观察者发现,对于每一行(或列)来说,按照确定后的阅读顺序读出的所有单词同时满足“自己的字典序不小于翻转后的字典序”,或同时满足“自己的字典序不大于翻转后的字典序”。
  在确定了所有行列的阅读顺序之后,我们可以构造出关于这种未知语言的字典。请问字典中出现的“翻转过来也是一个单词”的单词最少有多少个。请注意,如果一个单词翻转后是不同的另外一个单词,他们需要被分别计入;而对于本身是回文的单词则不需要重复计入。

格式

输入格式

  第一行一个正整数T,表示有T组测试数据。
  对于每一组数据来说:第一行输入两个整数N和M。
  第二行给出了N个数字,对应了N行,其中第i个数字若为1,则表示第i行的阅读顺序从左往右,若为-1,则表示阅读顺序从右往左,若为0,表示无法确定。第三行给出了M个数字,对应了M列,其中第i个数字若为1,则表示第i列的阅读顺序从上往下,若为-1,则阅读顺序从下往上,若为0,表示无法确定。
之后N行,每行给出了长度为M的字符串,由大写字母A到Z和下划线组成,对应了每一个格子内的符号,其中下划线表示这一个格子被留白。

输出格式

输出T行对应T组数据。每一组数据输出一行一个整数,表示最少有多少单词,满足翻转后依然是单词。请注意,一个单词如果是回文的,那么它一定满足“翻转后依然是单词”。

样例1

样例输入1

1
2 10
0 0
0 0 0 0 0 0 0 0 0 0
ADA_JARVIS
ADA_SIVRAJ

样例输出1

3

限制

对于20%的数据,1<=N,M<=10。
对于60%的数据,每行每列出现的单词不超过6个。
对于100%的数据,1<=N,M<=72,T<=64。

来源

SDOI 2016 round2 day1

信息

ID
1994
难度
5
分类
(无)
标签
递交数
33
已通过
14
通过率
42%
上传者

相关

在下列训练计划中:

RP++分类题库