| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 42 | 32 | 26 | 76.471% |
Охранное агентство получило контракт на охрану двух зданий. В каждом из зданий установлено множество камер видеонаблюдения.
Одна из стен комнаты охраны представляет собой прямоугольник, состоящий из $n$ горизонтальных рядов по $m$ видеомониторов в каждом. На каждый монитор выводится изображение с камеры, находящейся в одном из зданий. Комната охраны оборудована инновационным пультом управления с четырьмя кнопками: <<влево>>, <<вправо>>, <<вверх>> и <<вниз>>.
Кнопка <<влево>> перемещает изображение с каждого монитора на монитор, находящийся слева от него. При этом изображение из самого левого монитора в каждом ряду перемещается на самый правый монитор этого ряда.
Аналогичным образом действуют кнопки <<вправо>>, <<вверх>> и <<вниз>>. Кнопка <<вправо>> перемещает изображение с каждого монитора на монитор, находящийся справа от него. Изображения из самого правого монитора в каждом ряду перемещаются на самый левый монитор этого ряда. Кнопка <<вверх>> перемещает изображение с каждого из мониторов на монитор, находящийся над ним. Изображения из самого верхнего ряда перемещаются на мониторы самого нижнего ряда. Кнопка <<вниз>> перемещает изображение с каждого из мониторов на монитор, находящийся под ним. Изображения из самого нижнего ряда перемещаются на мониторы самого верхнего ряда.
Назовём блок мониторов размером 2ドル \times 2$ удобным для наблюдения, если они показывают изображения из одного и того же здания. В результате перемещения изображений по командам с пульта управления количество удобных для наблюдения блоков может изменяться. При этом один и тот же монитор может входить в несколько удобных для наблюдения блоков.
Требуется написать программу, определяющую максимальное количество удобных для наблюдения блоков, которое можно получить, управляя мониторами с пульта.
Первая строка входных данных содержит два целых числа $n$ --- количество рядов и $m$ --- количество мониторов в каждом ряду. Следующие $n$ строк описывают ряды мониторов в порядке сверху вниз. Каждая из этих строк содержит по $m$ символов, описывающих мониторы в соответствующем ряду в порядке слева направо. Символ <<1>> означает, что на монитор выводится изображение из первого здания, а символ <<2>> --- из второго здания.
Выходные данные должны содержать единственное целое число --- максимальное количество удобных для наблюдения блоков, которые можно получить, перемещая изображения на мониторах.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 37 | 2ドル \le n, m \le 50$ |
| 2 | 28 | 2ドル \le n, m \le 300$ |
| 3 | 35 | 2ドル \le n, m \le 1000$ |
2 4 1221 1221
2
3 2 22 22 22
2
3 3 111 121 111
3
В первом примере с помощью команды <<вправо>>, можно получить слева удобный для наблюдения блок из единиц, а справа --- удобный для наблюдения блок из двоек.
Во втором примере изначально на мониторе присутствуют два удобных для наблюдения блока.
В третьем примере, например, командами <<вправо>> и <<вниз>> можно добиться наличия трех удобных для наблюдения блоков из единиц.