問題一覧 > 通常問題

No.2689 Populous

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : SPD_9X2 / テスター : 👑 tute7627 👑 rin204 だれ arad kyawa
お気に入りにしたユーザー ProblemId : 10414 / 自分の提出
問題文最終更新日: 2024-03-18 14:24:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 422 (第1回 競技プログラミング講習会作問企画コンテスト) (順位表) の他の問題:

Problem Statement

There is an $H \times W$ grid.

Each cell on the outer boundary (a cell that shares an edge with at most 3 cells) has one integer written on it, and the cell in row $i$, column $j$ has the integer $A_{i,j}$ written on it.

Each cell not on the outer boundary (a cell that shares an edge with 4 cells) is an empty cell, with nothing written on it.

You fill in each empty cell so that the condition below is satisfied. In each cell, you write either # or one integer.

  • For every pair of adjacent (edge-sharing) cells, if both have integers written on them, the absolute difference between those numbers is at most 1.


Determine whether there is a way of filling that satisfies the condition. If there is, find the number, modulo $998244353$, of possible sets of positions where # is written when the number of written # is minimized.

Input

$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}$

  • All inputs are integers.
  • $3 \le H,W \le 1000$
  • $1 \le A_{i,j} \le 2000$

Output

If there is no way of filling, print -1.

If there is, print the number, modulo $998244353$, of possible sets of positions where # is written when the number of written # is minimized.

Print a newline at the end.

Sample

Sample 1
Input
3 5
1 1 2 2 1
1 2
2 1 1 1 1
Output
1

For example, the following filling satisfies the condition.

1 1 2 2 1
1 1 1 1 2
2 1 1 1 1
No # is placed, so there is 1 way.

Sample 2
Input
4 4
3 1 4 1
5 9
2 6
5 3 5 8
Output
-1

It is impossible because adjacent cells among the originally written numbers differ by more than 1.

Sample 3
Input
4 4
1 2 3 4
1 5
2 6
3 4 5 6
Output
4

For example, the following filling satisfies the condition.

1 2 3 4
1 # 4 5
2 3 # 6
3 4 5 6
There are 4 possible placements of #, so print 4.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。