/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
1,2,3,? からなる H 行 W 列のグリッド S が与えられます。上から i 行目、左から j 列目の文字は S_{i,j} です。
S の各 ? を 1,2,3 のいずれかに置き換えて得られるグリッドは ? の個数を q として 3^q 通りありますが、そのうち以下の条件を満たすものはいくつありますか？ 998244353 で割った余りを出力してください。
- 隣接する（辺を共有する）どの 2 つのマスにも異なる数字が書かれている。
制約
- 1\leq H,W
- H\times W\leq 200
- H,W は整数
- S は
1,2,3,?からなる H 行 W 列のグリッド
入力
入力は以下の形式で標準入力から与えられる。
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
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
S の各 ? を 1,2,3 のいずれかに置き換えて得られるグリッドはすべて条件を満たしません。
入力例 3
8 8 3?1????? ???1???? ??????2? ???????? ???????? ????13?? ??13?1?? ????????
出力例 3
779135038
Score : 575 points
Problem Statement
You are given a grid S with H rows and W columns consisting of 1, 2, 3, and ?. The character at the i-th row and j-th column is S_{i,j}.
By replacing each ? in S with 1, 2, or 3, we can obtain 3^q different grids, where q is the number of ?. Among these grids, how many satisfy the following condition? Print the count modulo 998244353.
- Any two adjacent (edge-sharing) cells contain different digits.
Constraints
- 1 \leq H, W
- H \times W \leq 200
- H and W are integers.
- S is a grid with H rows and W columns consisting of
1,2,3, and?.
Input
The input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
2 2 1? ??
Sample Output 1
6
Among the grids obtained by replacing each ? in S with 1, 2, or 3, the following six grids satisfy the condition.
12 12 12 13 13 13 21 23 31 21 31 32
Sample Input 2
2 3 123 3?1
Sample Output 2
0
None of the grids obtained by replacing ? satisfies the condition.
Sample Input 3
8 8 3?1????? ???1???? ??????2? ???????? ???????? ????13?? ??13?1?? ????????
Sample Output 3
779135038