← 返回题目列表

AtCoder · abc379_g

G. 计数网格 3 着色

中文机器翻译题面 查看原题

分数: 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