分数: 575 点
问题陈述
给你一个网格 S 与 H 行和 W 列组成 1, 2, 3,和 ?。角色位于 i第行和 j第列是 S_{i,j}.
通过替换每个 ? in S 与 1, 2,或 3,我们可以得到 3^q 不同的网格,其中 q 是数量 ?。在这些网格中,有多少个满足以下条件?打印计数模数 998244353.
- 任何两个相邻(共享边缘)的单元格包含不同的数字。
约束
- 1 \leq H, W
- H \times W \leq 200
- H 和 W 是整数。
- S 是一个网格 H 行和 W 列组成
1,2,3,和?.
输入
输入由标准输入按以下格式给出:
H W
S_{1,1}S_{1,2}\ldots S_{1,W}
S_{2,1}S_{2,2}\ldots S_{2,W}
\vdots
S_{H,1}S_{H,2}\ldots S_{H,W}
输出
打印答案。
示例输入 1
2 2 1? ??
示例输出 1
6
各替换得到的网格中 ? in S 与 1, 2,或 3,以下6个格子满足条件。
12 12 12 13 13 13 21 23 31 21 31 32
示例输入 2
2 3 123 3?1
示例输出 2
0
替换后没有得到任何网格 ? 满足条件。
示例输入 3
8 8 3?1????? ???1???? ??????2? ???????? ???????? ????13?? ??13?1?? ????????
示例输出 3
779135038