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/A

N/A

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


```