No.2689 Populous
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 1No
# 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 6There are 4 possible placements of
#, so print 4.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
SPD_9X2
tute7627
だれ
arad
kyawa