seuOJ551 - Royale Bataille

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2025

题目描述

Se battre pour la famille royale!

在公元四世纪的欧洲有两个帝国，一个在西北方向，另一个在东南方向，两个部落之间被一条河流隔开。这片土地是一个网格图，每片土地只能被任意一个帝国占有或者是河流。具体而言，使用数字 $1$ 代表被第一个帝国占有的土地，使用数字 $2$ 代表被第二个帝国占有的土地，数字 $0$ 代表河流，河流不属于任何一个帝国的土地。这片土地被使用的规则如下：

• 两个帝国的土地必须被河流完全隔开，即两片帝国的土地不能有公共边或者公共点（这很严重，不然会引发战争）。
• 任意一片第一个帝国的土地的西方（地图左侧）和北方（地图上侧）的土地只能是第一个帝国的土地。
• 任意一片第二个帝国的土地的东方（地图右侧）和南方（地图下侧）的土地只能是第二个帝国的土地。
• 任意一片是河流的土地的的西方（地图左侧）和北方（地图上侧）的土地只能是河流或者是第一个帝国的土地，东方（地图右侧）和南方（地图下侧）的土地只能是河流或者是第二个帝国的土地。

给你一张只由数字 $0,1,2$ 和 ? 组成的地图，? 代表不知道当前这片土地是什么，请你求出有多少种使用数字 $0,1,2$ 填充所有 ? 的方法，满足这篇土地的使用规则。因为方案数可能很多，请在输出方案数量时对于 $998244353$ 取模。

输入格式

第一行，一个整数 $t(1\le t\le 10^4)$，代表数据组数。

对于每组数据：

第一行，两个整数 $n,m(1\le n,m\le 4\cdot 10^4)$，分别代表地图的长和宽。

接下来连续的 $n$ 行，每行一个长度为 $m$ 的字符串，字符串的每个字符 $\red{c\in\{0,1,2,?\}}$，代表当前的地图。

保证同一测试点内的 $\red{n\times m}$ 的总和不超过 $4\cdot 10^4$。

输出格式

对于每组数据，输出一行数字，代表合法填充当前地图中所有的 ? 的方案数，将结果对于 $998244353$ 取模。

样例

输入样例

6
1 1
?
1 2
1?
3 3
11?
???
?22
8 10
1111110002
1111000002
111?????22
111???????
11???????2
??????????
????0?2222
0000222222
3 4
1102
1102
0022
2 2
??
??

输出样例

3
2
4
3100
0
11