CF1427G.One Billion Shades of Grey

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.

你需要用不同深浅的灰色来粉刷一面 $n\times n$ 的墙壁。该墙壁共有 $n$ 行瓷砖，每行有 $n$ 块瓷砖。

墙壁边界上的瓷砖（即第一行、最后一行、第一列和最后一列上的瓷砖）已被粉刷完毕，你不得更改它们的颜色。其余所有瓷砖均未粉刷。其中部分瓷砖已损坏，你不得粉刷这些损坏的瓷砖。题目保证：边界上的瓷砖均未损坏。

你需要粉刷所有未损坏且尚未粉刷的瓷砖。粉刷一块瓷砖时，你可以从 $10^9$ 种灰色中任选一种，这些灰色按编号 $1$ 至 $10^9$ 区分。允许多块瓷砖使用相同的灰色。形式化地说，粉刷整面墙壁等价于为每一块未损坏且尚未粉刷的瓷砖分配一个编号（即一个介于 $1$ 与 $10^9$ 之间的整数）。

两块瓷砖之间的对比度定义为它们所用灰色编号之差的绝对值。整面墙壁的总对比度定义为所有相邻的未损坏瓷砖对的对比度之和（两块瓷砖相邻当且仅当它们有一条公共边）。

请计算墙壁可能达到的最小总对比度。

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.

第一行包含一个整数 $n$（$3\le n\le 200$），表示方阵的行数与列数。

接下来是 $n$ 行，每行包含 $n$ 个整数。其中第 $i$ 行描述第 $i$ 行瓷砖的状态，包含 $n$ 个整数 $a_{ij}$（$-1\le a_{ij} \le 10^9$）。$a_{ij}$ 的值表示位于第 $i$ 行、第 $j$ 列的瓷砖状态：

• 若 $a_{ij}=0$，则该瓷砖未上色，需进行上色；
• 若 $a_{ij}=-1$，则该瓷砖已损坏，不可上色；
• 若 $1\le a_{ij}\le 10^9$，则该瓷砖已使用色号 $a_{ij}$ 完成上色。

保证：边界上的瓷砖均已上色；非边界位置的瓷砖均未上色；边界上的瓷砖均未损坏。

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

输出一个整数——墙壁的最小可能总对比度。

Explanation of the first testcase: The initial configuration of the tiles is (tiles to paint are denoted by ?):

1 7 6
4 ? 6
1 1 1

A possible way to paint the tile achieving the minimum possible contrast of $26$ is:

1 7 6
4 5 6
1 1 1

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 ?):

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

A possible way to paint the tiles achieving the minimum possible contrast of $34$ is:

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

第一个测试用例的说明：瓷砖的初始布局如下（待涂色的瓷砖用 ? 表示）：

1 7 6
4 ? 6
1 1 1

一种可实现最小可能对比度 $26$ 的涂色方案为：

1 7 6
4 5 6
1 1 1

第二个测试用例的说明：由于所有瓷砖均已涂色或已损坏，因此无需进行任何操作。总对比度为 $396$。

第三个测试用例的说明：瓷砖的初始布局如下（待涂色的瓷砖用 ? 表示）：

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

一种可实现最小可能对比度 $34$ 的涂色方案为：

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