Задача . C. Соединить

Алиса живет на плоской земле, которая может быть представлена как квадратная решетка \(n \times n\) со строками и столбцами, пронумерованными от \(1\) до \(n\). Обозначим клетку на пересечении строки \(r\) и столбца \(c\) упорядоченной парой \((r, c)\). Каждая клетка решетки является либо землей, либо водой.

Пример планеты с \(n = 5\). Она также является первым примером.

Алиса живет на клетке, которая является землей, \((r_1, c_1)\). Она хочет добраться до другой клетки, которая является землей, \((r_2, c_2)\). В любой момент она может переместиться в одну из соседних с ней ячеек — в одном из четырех направлений (т.е. вверх, вниз, влево или вправо).

К сожалению, Алиса не умеет плавать, и можно перемещаться только пешком (т.е. только по земле). В итоге путешествие Алисы может быть невозможно.

Чтобы помочь Алисе, вы хотите создать не более одного туннеля между какими-то двумя земляными клетками. Туннель позволяет Алисе перемещаться между двумя его концами. Создание туннеля требует некоторых затрат: стоимость туннеля между клетками \((r_s, c_s)\) и \((r_t, c_t)\) равна \((r_s-r_t)^2 + (c_s-c_t)^2\).

Таким образом, ваша задача — найти минимальную стоимость постройки не более одного туннеля так, чтобы Алиса смогла добраться от клетки \((r_1, c_1)\) до клетки \((r_2, c_2)\). Если постройка туннеля не обязательна, стоимость полагается равной \(0\).