One Billion Shades of Grey

题意翻译

给定一个 $n \times n$ 的棋盘，其边界上所有位置均填好了数字，你需要在剩余 $(n - 2) \times (n - 2)$ 个位置上填数，部分位置已经“破损”，在输入时用 $-1$ 描述，此处无法填数。 对于一种填数方案，定义一对相邻（四连通）的均不为“破损”的格子的贡献为其填入的数字的差值的绝对值，定义此填数方案的权值为各个相邻的格子的贡献之和。 你需要最小化权值，输出可以得到的最小权值。 保证 $3 \le n \le 200$，$-1 \le a_{i, j} \le {10}^9$。 - 保证边界上的方格均未“破损”。

题目描述

You have to paint with shades of grey the tiles of an $ n\times n $ wall. The wall has $ n $ rows of tiles, each with $ n $ tiles. The tiles on the boundary of the wall (i.e., on the first row, last row, first column and last column) are already painted and you shall not change their color. All the other tiles are not painted. Some of the tiles are broken, you shall not paint those tiles. It is guaranteed that the tiles on the boundary are not broken. You shall paint all the non-broken tiles that are not already painted. When you paint a tile you can choose from $ 10^9 $ shades of grey, indexed from $ 1 $ to $ 10^9 $ . You can paint multiple tiles with the same shade. Formally, painting the wall is equivalent to assigning a shade (an integer between $ 1 $ and $ 10^9 $ ) to each non-broken tile that is not already painted. The contrast between two tiles is the absolute value of the difference between the shades of the two tiles. The total contrast of the wall is the sum of the contrast of all the pairs of adjacent non-broken tiles (two tiles are adjacent if they share a side). Compute the minimum possible total contrast of the wall.

输入输出格式

输入格式

The first line contains $ n $ ( $ 3\le n\le 200 $ ) – the number of rows and columns. Then $ n $ lines, each containing $ n $ integers, follow. The $ i $ -th of these lines describe the $ i $ -th row of tiles. It contains the $ n $ integers $ a_{ij} $ ( $ -1\le a_{ij} \le 10^9) $ . The value of $ a_{ij} $ described the tile on the $ i $ -th row and $ j $ -th column: - If $ a_{ij}=0 $ , then the tile is not painted and shall be painted. - If $ a_{ij}=-1 $ , then the tile is broken and shall not be painted. - If $ 1\le a_{ij}\le 10^9 $ , then the tile is already painted with the shade $ a_{ij} $ . It is guaranteed that the tiles on the boundary are already painted, the tiles not on the boundary are not already painted, and the tiles on the boundary are not broken.

输出格式

Print a single integer – the minimum possible total contrast of the wall.

输入输出样例

输入样例 #1

3
1 7 6
4 0 6
1 1 1

输出样例 #1

26

输入样例 #2

3
10 100 1
1 -1 100
10 10 10

输出样例 #2

396

输入样例 #3

5
6 6 5 4 4
6 0 0 0 4
7 0 0 0 3
8 0 0 0 2
8 8 1 2 2

输出样例 #3

34

输入样例 #4

7
315055237 841510063 581663979 148389224 405375301 243686840 882512379
683199716 -1 -1 0 0 0 346177625
496442279 0 0 0 0 0 815993623
223938231 0 0 -1 0 0 16170511
44132173 0 -1 0 0 0 130735659
212201259 0 0 -1 0 0 166102576
123213235 506794677 467013743 410119347 791447348 80193382 142887538

输出样例 #4

10129482893

说明

Explanation of the first testcase: The initial configuration of the tiles is (tiles to paint are denoted by ?): ``` <pre class="verbatim"><br></br>1 7 6<br></br>4 ? 6<br></br>1 1 1<br></br> ``` A possible way to paint the tile achieving the minimum possible contrast of $ 26 $ is: ``` <pre class="verbatim"><br></br>1 7 6<br></br>4 5 6<br></br>1 1 1<br></br> ``` Explanation of the second testcase: Since all tiles are either painted or broken, there is nothing to do. The total contrast is $ 396 $ . Explanation of the third testcase: The initial configuration of the tiles is (tiles to paint are denoted by ?): ``` <pre class="verbatim"><br></br>6 6 5 4 4<br></br>6 ? ? ? 4<br></br>7 ? ? ? 3<br></br>8 ? ? ? 2<br></br>8 8 1 2 2<br></br> ``` A possible way to paint the tiles achieving the minimum possible contrast of $ 34 $ is: ``` <pre class="verbatim"><br></br>6 6 5 4 4<br></br>6 6 5 4 4<br></br>7 7 5 3 3<br></br>8 8 2 2 2<br></br>8 8 1 2 2<br></br> ```