問題一覧 > 通常問題

No.2328 Build Walls

レベル : / AI推定難易度 : 1525 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 95
作問者 : dyktr_06 / テスター : tyawanmusi hikikomori sepa38 Seed57_cash
お気に入りにしたユーザー ProblemId : 9515 / 自分の提出
問題文最終更新日: 2023-05-26 23:18: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
MMA Contest 015 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。