32053번 - Blocking the Way 다국어

문제

Alice is playing a puzzle game where she slides a tile piece to move it to its destination on a rectangular grid board consisting of unit squares. Only parallel moves of the piece on the game board are allowed; no rotations nor lifting up. Some squares on the board are marked no-entry where any parts of the tile piece should not enter.

The tile piece is composed of a number of unit squares joined tightly along their edges. The tile piece is initially placed to touch both the left and the top ends of the board. The goal of Alice is to slide the tile piece to make it touch both the right and the bottom ends of the board.

Bob, on the other hand, wants to make Alice's goal unachievable by changing some squares to no-entry. Each square, except for those initially covered by the tile piece, can be made no-entry by paying the specified number of coins. Compute the minimum number of coins Bob has to pay in total to make Alice's goal unachievable.

입력

The input consists of multiple datasets, each in the following format.

r c

a_1,1 ⋯ a_1,c

⋮

a_r,1 ⋯ a_r,c

Here, r and c are integers between 2 and 100, inclusive, representing the numbers of rows and columns of the board, respectively. The following a_i,j (1 ≤ i ≤ r, 1 ≤ j ≤ c) are integers between −1 and 10⁹, inclusive. Here, a_i,j represents the state of the square (i, j) on row i and column j, as follows.

• If a_i,j = −1, the square is initially covered by the tile piece.
• If a_i,j = 0, the square is no-entry from the beginning.
• If a_i,j > 0, Bob can make the square no-entry by paying a_i,j coins.

The number of (i, j) satisfying a_i,j = −1 is between 1 and 100, inclusive. All the squares corresponding to them are connected directly or indirectly with one or more of their edges. Furthermore, they are contiguous in each row and each column. That is, if a_i,j1 = −1 and a_i,j2 = −1 for two columns j₁ and j₂ in the same row i where j₁ < j₂, then a_i,j = −1 for all j such that j₁ < j < j₂. Similarly, if a_i1,j = −1 and a_i2,j = −1 for two rows i₁ and i₂ in the same column j where i₁ < i₂, then a_i,j = −1 for all i such that i₁ < i < i₂.

It is guaranteed that, in the initial state, the tile piece is placed so that some of its edges touch the left end of the board and some touch the top end. It is also guaranteed that Alice has not yet achieved her goal. That is, the following two conditions are satisfied.

• There exists at least one i satisfying a_i,1 = −1 and at least one j satisfying a_1,j = −1.
• a_i,c ≠ −1 for all i or a_r,j ≠ −1 for all j.

The end of the input is indicated by a line consisting of two zeros. The number of datasets does not exceed 50. The sum of r of all the datasets does not exceed 1000. The sum of c of all the datasets does not exceed 1000. The total number of (i, j) satisfying a_i,j = −1 of all the datasets does not exceed 1000.

출력

For each dataset, output on a single line the minimum number of coins Bob has to pay.

제한

힌트