[Sdoi2016]墙上的句子
时间限制：10s 空间限制：128MB
题目描述
考古学家发现了一堵写有未知语言的白色墙壁，上面有一个n行m列的格子，其中有些格子内被填入了某个A至Z的大
写字母，还有些格子是空白的。一直横着或竖着的连续若干个字母会形成一个单词，且每一行的阅读顺序可能是从
左向右或从右向左，每一列的阅读顺序可能是从下往上或从上往下。也就是说对于每一行来说，从左向右可以被看
做是若干个单词形成的句子，相邻两个单词被一个或多个空白格子分割开来；也有可能是从右向左被看成是一个句
子，竖直方向类似。遗憾的是，我们并不完全知道每一行每一列的阅读顺序是怎样的。但可以猜测，有些单词会满
足反转过来也是一个单词。例如单词BOY，翻转过来的YOB也是一个英文单词。此外观察者发现，对每一行（列）来
说，按照确定后的阅读顺序读出的所有单词同时满足“自己的字典序不小于翻转后的字典序”，或同时满足“自己
的字典序不大于翻转后的字典序”。在确定了所有行列的阅读顺序之后，我们可以构造出关于这种未知语言的字典
。请问字典中出现的“翻转过来也是一个单词”的单词最少有多少种请注意，如果一个单词翻转后是不同的另外一
个单词，它们需要被分别计入；而对于本身是回文的单词则不需要重复计入
输入格式
第一行一个整数T，表示T组测试数据。
对于每一组数据来说：第一行输入两个整数n,m。
第二行给出了n个数字，对应n行，其中若第i个数字为1，则表示第i行的阅读顺序从左往右；若为-1则为从右向左
；若为0则表示无法确定
第三行给出了m个数字，对应n行，其中若第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 对于100%的数据，1<=n,m<=72,t<=64< pre="">提示
没有写明提示
题目来源
By AHdoc命题 鸣谢Loi_DQS上传，xiaoyimi提供题面