レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : 👑 SPD_9X2 / テスター : 👑 tute7627 👑 rin204 だれ arad kyawa

4 Tweet ProblemId : 10414 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-03-18 14:24:14

問題文

$H \times W$ のマス目があります。

外周のマス(辺を共有するマスが3個以下のマス)にはぞれぞれ整数が1つずつ書かれていて、$i$ 行目, $j$列目のマスには整数 $A_{i,j}$ が書かれています。

外周以外のマス(4つのマスと辺を共有するマス)は空マスで、何も書かれていません。

下の条件を満たしつつ、それぞれの空マスに記入を行います。各マスには、# か、整数を1つ書き込みます。

• すべての隣接(辺を共有)するマスの組について、両者共に整数が書かれているならば、書かれた数の差の絶対値は1以下である

条件を満たす書き込み方があるか判定してください。書き込む方法があるのならば、# を書き込む個数を最小化した場合の、# を書き込む位置の集合として考えられる場合の数を $998244353$ で割った余りを求めてください。

$H\ W$
$A_{1,1}\ A_{1,2}\ \cdots\ A_{1,W-1}\ A_{1,W}$
$A_{2,1}\ A_{2,W}$
$\vdots$
$A_{H-1,1}\ A_{H-1,W}$
$A_{H,1}\ A_{H,2}\ \cdots\ A_{H,W-1}\ A_{H,W}$

3 5
1 1 2 2 1
1 2
2 1 1 1 1

1

1 1 2 2 1
1 1 1 1 2
2 1 1 1 1

4 4
3 1 4 1
5 9
2 6
5 3 5 8

-1

4 4
1 2 3 4
1 5
2 6
3 4 5 6

4

1 2 3 4
1 # 4 5
2 3 # 6
3 4 5 6