No.2328 Build Walls
タグ : / 解いたユーザー数 95
作問者 :
hikikomori
sepa38
Seed57_cash
Problem Statement
There is a town divided into road cells arranged in a grid with $H$ rows and $W$ columns.
Sepa starts from one of the cells in the $1$-st row from the top and is trying to reach one of the cells in the $H$-th row.
From the cell he is in, Sepa can move to a road cell adjacent vertically or horizontally.
Yakitori has decided to build walls so that Sepa cannot reach any of the cells in the $H$-th row.
However, the following rules must be followed when building walls.
- Walls cannot be placed on cells in the $1$-st row or the $H$-th row.
- Building a wall on the cell in the $i$-th row from the top and the $j$-th column from the left $(2 \leq i \leq H - 1, 1 \leq j \leq W)$ costs $A_{i,j}$. However, if $A_{i,j} = -1$, a wall cannot be placed on that cell.
Find the minimum cost of placing walls so that Sepa cannot reach any of the cells in the $H$-th row.
If Sepa can reach one of the cells in the $H$-th row no matter how the walls are placed, output $-1$.
Constraints
- $3 \leq H, W \leq 800$
- $1 \leq A_{i,j} \leq 800$ or $A_{i,j} = -1$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$H$ $W$
$A_{2,1}$ $A_{2,2}$ ... $A_{2,W}$
$A_{3,1}$ $A_{3,2}$ ... $A_{3,W}$
$\vdots$
$A_{H-1,1}$ $A_{H-1,2}$ ... $A_{H-1,W}$
Output
Output the answer to the problem on one line.
If Sepa can reach one of the cells in the $H$-th row no matter how the walls are placed, output $-1$.
Sample
Sample 1
Input
5 4 2 5 7 11 1 6 9 10 3 4 8 12
Output
23
Denoting road cells by . and cells with walls by #, the following placement, for example, is optimal.
.... .... #..# .##. ....
Sample 2
Input
5 4 2 5 -1 11 -1 6 9 10 3 -1 8 12
Output
26
For example, the following placement is optimal.
.... #... .#.# ..#. ....
Sample 3
Input
5 4 2 5 -1 11 -1 -1 -1 10 3 -1 8 12
Output
-1
No matter how the walls are placed, Sepa ends up reaching a cell in the $H$-th row.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。