Определить время, необходимое для того, чтобы все грызуны покинули комнату

В комнату размером N * N маленьких плиток было размещено K грызунов. Кроме того, в комнате есть M отверстий в полу, через которые грызуны могут выбраться из нее. Грызуну нужна ровно одна миллисекунда для того чтобы переместиться с некоторой плитки в соседнюю (которая имеет с данной общую сторону).

КАЖДЫЙ грызун хочет как можно быстрее выбраться из комнаты и сразу начинает двигаться к ближайшему выходу. Грызуны достаточно маленькие, поэтому в каждый момент времени на одной плитке может находиться сколь угодно много грызунов. К тому тому же они не будут мешать или замедлять друг друга. Также на некоторых плитках может быть более одного открытых отверстий.

Вам нужно определить время, необходимое для того, чтобы все грызуны покинули комнату. Заметьте, что возможна ситуация когда грызун с самого начала находится на плитке с выходом. В таком случае ему нужно 0 миллисекунд чтобы покинуть комнату.

Ввод

Первая строка содержит целое число N (1 <= N <= 1000) - размер комнаты.
Следующая строка содержит количество грызунов - K (1 <= K <= 1000).
Следующие K строк содержат по два числа Xi, Yi - координаты грызунов.
Следующая строка содержит количество отверстий выхода - M (1 <= M <= 1000).
Следующие M строк содержат по два числа Xi, Yi (1 <= Xi, Yi <= N) - координаты отверстий выхода.

Вывод

Единственное число - необходимое время в миллисекундах

0

Имхо, просто надо найти максимальное расстояние от грызуна до выхода в метрике D = |Xa - Xb| + |Ya - Yb| (если я, конечно, правильно понял нагроможденное условие, вызывающее у нормального человека легкое подташнивание)
Ничего лучше тупого перебора я не вижу. Вычислительная сложность N*N*M <= 10⁹ для современного компьютера вполне преодолима, тем более, что все вычисления в целых числах.

0