(Е. Джобс) Игра «Заполни поле» заключается в том, чтобы заполнить прямоугольное поле, разбитое на квадраты. Игрок хочет написать программу, которая определила бы сколько есть позиций, в которые можно поместить горизонтальные блоки из четырех квадратов.
Входные данные представлены в файле 26-72.txt следующим образом. В первой строке записаны три числа N, M, K -- размер поля по горизонтали, размер поля по вертикали и количество занятых на поле квадратов. В каждой из следующих K строк записана пара чисел -- номера строки и столбца занятого квадрата.
Программа должна вывести пару чисел -- количество позиций в которые можно разместить горизонтальную линию из четырёх квадратов и номер ряда, в котором находится максимальное количество позиций для такого размещения. Если таких рядов несколько, выводится минимальный возможный номер.
Пример входного файла:
7 6 10
1 1
1 5
2 5
2 6
3 1
3 7
5 2
6 3
6 5
6 7
После анализа пар можем прийти к выводу, что имеем дело со следующим полем:
Расположить линию из четырех квадратов можно в 9 позициях (2;1), (3; 2), (3; 3), (4; 1), (4; 2), (4; 3), (4; 4), (5; 3), (5; 4). Максимальное количество позиций (4), в которых можно расположить фигуру, в 4 ряду. Ответ: 9 4.