Задача №113221. Управление видеонаблюдением
Охранное агентство получило заказ на обеспечение видеонаблюдения двух зданий. В каждом из зданий установлено множество видеокамер.
На одной из стен зала видеонаблюдения расположена панель, представляющая собой прямо- угольник, состоящий из \(n\) горизонтальных рядов по \(m\) мониторов в каждом. На каждый монитор выводится изображение с камеры, находящейся в одном из зданий. Зал видеонаблюдения оборудован инновационным пультом управления с четырьмя кнопками: «влево», «вправо», «вверх» и «вниз».
Кнопка «влево» перемещает изображение с каждого монитора на монитор, находящийся слева от него. При этом изображение из самого левого монитора в каждом ряду перемещается на самый правый монитор этого ряда.
Аналогичным образом действуют кнопки «вправо», «вверх» и «вниз». Кнопка «вправо» перемещает изображение с каждого монитора на монитор, находящийся справа от него. Изображения из самого правого монитора в каждом ряду перемещаются на самый левый монитор этого ряда. Кнопка «вверх» перемещает изображение с каждого из мониторов на монитор, находящийся над ним. Изображения из самого верхнего ряда перемещаются на мониторы самого нижнего ряда. Кнопка «вниз» перемещает изображение с каждого из мониторов на монитор, находящийся под ним. Изображения из самого нижнего ряда перемещаются на мониторы самого верхнего ряда.
Назовём блок мониторов размером \(2 \times 2\) удобным для наблюдения, если эти мониторы показывают изображения из одного и того же здания. В результате перемещения изображений по командам с пульта управления количество удобных для наблюдения блоков может изменяться. При этом один и тот же монитор может входить в несколько удобных для наблюдения блоков.
Требуется написать программу, определяющую максимальное количество удобных для наблюдения блоков, которое можно получить, управляя мониторами с пульта.
Первая строка входных данных содержит два целых числа: \(n\) — количество рядов и \(m\) — количество мониторов в каждом ряду (\(2 \le n, m \le 1000\)). Следующие \(n\) строк описывают ряды мониторов в порядке сверху вниз. Каждая из этих строк содержит по \(m\) символов, описывающих мониторы в соответствующем ряду в порядке слева направо. Символ «1» означает, что на монитор выводится изображение из первого здания, а символ «2» — из второго здания.
Выходные данные должны содержать единственное целое число — максимальное количество удобных для наблюдения блоков, которые можно получить, перемещая изображения на мониторах.
В первом примере с помощью команды «вправо», можно получить слева удобный для наблюдения блок из единиц, а справа — удобный для наблюдения блок из двоек.
Во втором примере изначально на мониторе присутствуют два удобных для наблюдения блока.
В третьем примере, например, командами «вправо» и «вниз» можно добиться наличия трёх удобных для наблюдения блоков из единиц.
2 4 1221 1221
2
3 2 22 22 22
2
3 3 111 121 111
3