printРабочее место участника

printЗадачи

1444. Модель Изинга

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Модель Изинга используется в физике для описания твердого тела. Она использует представление кристаллической решетки, в узлах которой находятся атомы.
Рассмотрим плоскую прямоугольную решетку с `N` узлами по вертикали и `M` узлами по горизонтали (всего `"NM"` узлов). Каждый узел характеризуется своим спином, который может принимать значения `+1` или `-1`.
Соседними считаются узлы решётки, смежные по горизонтали или вертикали. Назовём энергией решетки количество пар соседних узлов с различными спинами.
Дана решётка с известными спинами в каждом узле. Требуется поменять спины ровно двух различных узлов на противоположные таким образом, чтобы энергия полученной решетки была максимальна. Если существует несколько решений, вывести любое из них.
Энергия решетки, приведенной в примере, равна 13. После изменения спина левого верхнего узла и третьего узла во второй строке получим решетку с энергией 15.
Формат входного файла
В первой строке входного файла содержатся числа `N` и `M`. Далее следует `N` строк по `M` символов в каждой. Строки состоят из символов '+' и '-'. Символ '+' соответствует положительному спину, а '-'  – отрицательному.
Формат выходного файла
В выходной файл выведите четыре числа: `r_1\ c_1\ r_2\ c_2`  – координаты двух узлов, изменение спина в которых максимально увеличит энергию. `r_i`  – номер строки узла, `c_i`  – номер узла в его строке. Нумерация начинается с 1.
Ограничения
`1\ ≤\ N,\ M\ ≤\ 1000`; `N+M\ >\ 2`;

Пример ввода

3 4
+-+-
-+++
+-+-

Пример вывода

1 1 2 3
Источник: Отборочные соревнования ВКОШП Дальневосточного региона, 2009
loading