Codeforces Global Round 11 |
---|
Закончено |
Вы должны покрасить оттенками серого плитки стены размера $$$n\times n$$$. Стена состоит из $$$n$$$ рядов плиток, в каждом по $$$n$$$ плиток.
Плитки на границе стены (т.е. в первом ряду, последнем ряду, первом столбце и последнем столбце) уже покрашены, и вы не должны менять их цвет. Все остальные плитки не покрашены.
Некоторые из плиток сломаны, их нельзя красить. Гарантируется, что плитки на границе не сломаны.
Вы должны покрасить все не сломанные плитки, которые еще не покрашены. Когда вы красите плитку, вы можете выбрать один из $$$10^9$$$ оттенков серого, пронумерованных от $$$1$$$ до $$$10^9$$$. Вы можете покрасить несколько плиток одним и тем же оттенком. Формально, раскраска стены эквивалентна присвоению оттенка (целое число от $$$1$$$ до $$$10^9$$$) каждой неокрашенной плитке, которая еще не закрашена.
Контраст между двумя плитками равен модулю разности между оттенками двух плиток. Общий контраст стены является суммой контрастов по всем парам соседних несломанных плиток (две плитки соседние, если они имеют общую сторону).
Вычислите минимально возможный суммарный контраст стены.
Первая строка содержит $$$n$$$ ($$$3\le n\le 200$$$) — количество строк и столбцов.
Затем следуют $$$n$$$ строк, каждая из которых содержит $$$n$$$ целых чисел. $$$i$$$-я из этих строк описывает $$$i$$$-ю строку плиток. Она содержит $$$n$$$ целых чисел $$$a_{ij}$$$ ($$$-1\le a_{ij} \le 10^9)$$$. Значение $$$a_{ij}$$$ описывает плитку в $$$i$$$-й строке и $$$j$$$-м столбце:
Выведите единственное целое число — минимально возможный суммарный контраст стены.
3 1 7 6 4 0 6 1 1 1
26
3 10 100 1 1 -1 100 10 10 10
396
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
34
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
10129482893
Пояснение первого примера: Первоначальная конфигурация плиток (плитки, которые нужно покрасить, обозначаются ?):
1 7 6
4 ? 6
1 1 1
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
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
Название |
---|