CF1427G One Billion Shades of Grey

你需要用不同深浅的灰色给一个 $n\times n$ 的墙上的瓷砖上色。墙有 $n$ 行，每行有 $n$ 块瓷砖。 墙的边界上的瓷砖（即第一行、最后一行、第一列和最后一列）已经被涂色，且你不能更改它们的颜色。其他瓷砖尚未上色。其中有些瓷砖是坏的，你不能给这些瓷砖上色。保证边界上的瓷砖没有坏的。 你需要给所有未损坏且尚未上色的瓷砖上色。每次上色时，你可以从 $10^9$ 种灰色中任选一种，编号为 $1$ 到 $10^9$。你可以给多块瓷砖涂相同的颜色。形式上，上色等价于给每个未损坏且未上色的瓷砖分配一个色号（$1$ 到 $10^9$ 之间的整数）。 两块瓷砖的对比度定义为它们颜色编号之差的绝对值。墙的总对比度是所有相邻且未损坏瓷砖对之间的对比度之和（两块瓷砖相邻当且仅当它们有公共边）。 请计算墙的最小可能总对比度。

第一行包含一个整数 $n$（$3\le n\le 200$）——行数和列数。 接下来 $n$ 行，每行包含 $n$ 个整数，描述瓷砖的初始状态。第 $i$ 行第 $j$ 列的整数 $a_{ij}$（$-1\le a_{ij}\le 10^9$）表示： - 如果 $a_{ij}=0$，该瓷砖未上色，需要上色。 - 如果 $a_{ij}=-1$，该瓷砖是坏的，不能上色。 - 如果 $1\le a_{ij}\le 10^9$，该瓷砖已经用色号 $a_{ij}$ 上色。 保证边界上的瓷砖都已经上色，非边界上的瓷砖都未上色，边界上的瓷砖没有坏的。

输出一个整数，表示墙的最小可能总对比度。

第一个样例解释：初始瓷砖配置如下（待上色用 ? 表示）： ``` 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 ``` 由 ChatGPT 4.1 翻译