#P18270. Norte da Universidade
Norte da Universidade
Norte da Universidade
题目描述
一些大学用坐标方位给校园建筑命名:把校园划分为北、南、西、东四个区域,再给每个区域中的建筑编号。由于历史或地理原因,一个区域可能不连通,也可能完全不存在。这种划分只须满足以下规则:
- 北区
N中任意建筑的正北方,所有建筑都必须属于北区。 - 南区
S中任意建筑的正南方,所有建筑都必须属于南区。 - 东区
E中任意建筑的正东方,所有建筑都必须属于东区。 - 西区
W中任意建筑的正西方,所有建筑都必须属于西区。
今天 Aki 参观了一所遵循这种命名规则的大学。他发现校园的建筑恰好排列成一个 的网格,每格一栋建筑。他已经知道部分建筑所属的区域,其余建筑所属的区域尚不清楚。
请计算与已知信息相容、且满足四条规则的校园布局有多少种。只要存在一栋建筑在两种布局中所属的区域不同,这两种布局就不同。答案对 取模。
下图对应第一个样例。左边是已知地图,中间是一个合法的补全方案,右边是不合法的方案。例如右图第三行最后三格违背东区规则:一个 E 的正东方出现了 N。

网格从北到南排列 行,从西到东排列 列,左上角是西北角。“正北方”等仅指同一列或同一行上对应方向的格子。每个 ? 必须替换为四种字母之一;已给定的字母不能修改。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例先输入一行两个整数 。接下来 行,每行一个长度为 的字符串,字符只能为 N、S、W、E 或 ?。其中 ? 表示未知区域。
输出格式
每个测试用例输出一行一个整数,表示合法布局数对 取模的结果。如果已知信息互相矛盾,输出 。
数据范围
- 。
- 。
- 每个输入文件中,所有测试用例的 之和不超过 。
样例
5
11 5
NNNNN
NN???
WW???
WWEEE
WEEEE
WEEEE
WWEEE
WWEE?
SSSSS
?SSS?
??SS?
2 7
??S?N??
??S?N??
3 4
W??E
WEEE
?E??
2 2
??
??
3 3
???
???
???
26
1587
18
56
1112