Задача №114893. Огород Марио
Позади много хороших дел: Марио уже спас принцессу, выиграл гонки и подарил подарок Луиджи. Конечно же, впереди ещё больше хороших дел, однако сейчас наш герой отправляется в заслуженный отпуск! Марио — русский человек, а потому он решил провести отпуск в своем любимом огороде.
Огород представляет собой прямоугольник r × c , разделенный на rc единичных клеток. Строки огорода пронумерованы целыми числами от 1 до r в направлении с севера на юг, а столбцы пронумерованы целыми числами от 1 до c в направлении с запада на восток. Марио решил посадить у себя в огороде картошку. Он уже выбрал n клеток и посадил по клубню в каждую из них.
Не успел Марио налить себе кружечку кваса в ожидании урожая, как из ниоткуда появился Боузер и превратил каждый посаженный клубень в гриб Гумба! Как известно, эти грибы очень быстро распространяются. Назовем клетку зараженной , если в ней уже появился Гумба. В момент превращения все клетки, в которые была посажена картошка, становятся зараженными. После этого каждую секунду происходит заражение новых клеток: каждая клетка, соседняя по стороне хотя бы с одной зараженной клеткой, тоже становится зараженной. Обратите внимание, что если клетка однажды была заражена, она будет зараженной все оставшееся время с этого момента.
Разумеется, Марио просто так не одолеть, и у него есть специальное средство против грибов Гумба, однако прежде чем уничтожить все грибы и заново посадить картошку, Марио заинтересовал вопрос: через сколько секунд впервые после момента превращения все клетки огорода будут заражены. Марио быстро смог ответить на свой же вопрос, попытайтесь и вы за ним поспеть.
Первая строка входных данных содержит два целых числа r и c — размеры огорода Марио ( 1 ≤ r , c ≤ 10 8 ). Вторая строка входных данных содержит единственное целое число n — количество посаженных клубней ( 1 ≤ n ≤ 15 000 ). Следующие n строк описывают клетки, в которые была посажена картошка. Каждая из них содержит два целых числа x i и y i — номер строки и столбца, на пересечении которых находится очередная клетка, в которую Марио посадил очередной клубень ( 1 ≤ x i ≤ r , 1 ≤ y i ≤ c ). Гарантируется, что все эти клетки различны.
Выведите единственное целое число — минимальное время в секундах, через которое все клетки огорода будут заражены. Если все клетки огорода будут заражены уже в момент превращения, выведите число 0 .
Эта задача состоит из восьми подзадач. Для подзадач выполняются дополнительные ограничения, указанные в таблице ниже. Для получения баллов за подзадачу необходимо пройти все тесты данной подзадачи, а также все тесты всех необходимых подзадач. Необходимые подзадачи также указаны в таблице.
| Ограничения | ||||
| Подзадача | Баллы | n | r , c | Необходимые подзадачи |
| 1 | 10 | n = 1 | 1 ≤ r , c ≤ 10 8 | – |
| 2 | 5 | 1 ≤ n ≤ 50 | 1 ≤ r , c ≤ 50 | – |
| 3 | 10 | 1 ≤ n ≤ 300 | 1 ≤ r , c ≤ 300 | 2 |
| 4 | 10 | 1 ≤ n ≤ 2000 | 1 ≤ r , c ≤ 2000 | 2, 3 |
| 5 | 20 | 1 ≤ n ≤ 2000 | 1 ≤ r , c ≤ 10 8 | 2, 3, 4 |
| 6 | 10 | 1 ≤ n ≤ 15 000 | 1 ≤ r , c ≤ 2000 | 2, 3, 4 |
| 7 | 25 | 1 ≤ n ≤ 15 000 | 1 ≤ r , c ≤ 10 5 | 2, 3, 4, 6 |
| 8 | 10 | 1 ≤ n ≤ 15 000 | 1 ≤ r , c ≤ 10 8 | 1, 2, 3, 4, 5, 6, 7 |
3 4 2 1 2 3 4
3