QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 4107. 墙上的句子

Statistics

考古学家发现了一堵写有未知语言的白色墙壁,上面有一个 nm 列的格子,其中有些格子内被填入了某个 A 至 Z 的大写字母,还有些格子是空白的。一直横着或竖着的连续若干个字母会形成一个单词,且每一行的阅读顺序可能是从左向右或从右向左,每一列的阅读顺序可能是从下往上或从上往下。也就是说对于每一行来说,从左向右可以被看做是若干个单词形成的句子,相邻两个单词被一个或多个空白格子分割开来;也有可能是从右向左被看成是一个句子,竖直方向类似。

遗憾的是,我们并不完全知道每一行每一列的阅读顺序是怎样的。但可以猜测,有些单词会满足反转过来也是一个单词。例如单词 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 行。每一组数据输出一行一个整数,表示最少有多少个单词,满足翻转后依然是单词。

注意,如果一个单词是回文,那么它一定满足「翻转后依旧是单词」。

样例数据

样例输入

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

样例输出

3

子任务

测试点 n,m
12 9
34 18
56 24
710 72

对于 100% 的数据,1n,m72, T64