#P18270. Norte da Universidade

Norte da Universidade

Norte da Universidade

题目描述

一些大学用坐标方位给校园建筑命名:把校园划分为北、南、西、东四个区域,再给每个区域中的建筑编号。由于历史或地理原因,一个区域可能不连通,也可能完全不存在。这种划分只须满足以下规则:

  • 北区 N 中任意建筑的正北方,所有建筑都必须属于北区。
  • 南区 S 中任意建筑的正南方,所有建筑都必须属于南区。
  • 东区 E 中任意建筑的正东方,所有建筑都必须属于东区。
  • 西区 W 中任意建筑的正西方,所有建筑都必须属于西区。

今天 Aki 参观了一所遵循这种命名规则的大学。他发现校园的建筑恰好排列成一个 n×mn\times m 的网格,每格一栋建筑。他已经知道部分建筑所属的区域,其余建筑所属的区域尚不清楚。

请计算与已知信息相容、且满足四条规则的校园布局有多少种。只要存在一栋建筑在两种布局中所属的区域不同,这两种布局就不同。答案对 998244353998244353 取模。

下图对应第一个样例。左边是已知地图,中间是一个合法的补全方案,右边是不合法的方案。例如右图第三行最后三格违背东区规则:一个 E 的正东方出现了 N。

原题中的地图、合法补全和非法补全

网格从北到南排列 nn 行,从西到东排列 mm 列,左上角是西北角。“正北方”等仅指同一列或同一行上对应方向的格子。每个 ? 必须替换为四种字母之一;已给定的字母不能修改。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例先输入一行两个整数 n,mn,m。接下来 nn 行,每行一个长度为 mm 的字符串,字符只能为 N、S、W、E 或 ?。其中 ? 表示未知区域。

输出格式

每个测试用例输出一行一个整数,表示合法布局数对 998244353998244353 取模的结果。如果已知信息互相矛盾,输出 00。

数据范围

  • 1≤T≤1001\le T\le100。
  • 1≤n,m≤10001\le n,m\le1000。
  • 每个输入文件中,所有测试用例的 n×mn\times m 之和不超过 2×1062\times10^6。

样例

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