1. Идея

Дана прямоугольная сетка n × m и несколько стартовых клеток.
Нужно найти такую клетку, до которой минимальное расстояние до ближайшей стартовой клетки максимально.
Расстояние измеряется по Манхэттену, то есть за один шаг можно перейти вверх, вниз, влево или вправо.

Если посмотреть на задачу как на распространение волны, то все стартовые клетки начинают «расти» одновременно.
На первом шаге они захватывают соседей, на втором — соседей соседей и так далее.

Тогда:

• клетка, в которую волна придёт позже всего, и есть ответ;
• расстояние до ближайшего источника равно моменту первого посещения клетки.

Это классическая задача на поиск кратчайших расстояний от нескольких источников сразу, а значит, её удобно решать мульти-источниковым BFS.

2. Наблюдения

Наблюдение 1. Манхэттенское расстояние и BFS

На сетке, где разрешены только переходы в 4 стороны, кратчайшее число шагов между клетками как раз равно длине кратчайшего пути по рёбрам сетки.
Значит, BFS естественным образом считает нужные расстояния.

Наблюдение 2. Несколько источников

Если запустить BFS сразу из всех заданных клеток, положив их в очередь в самом начале, то:

• каждая клетка будет посещена на минимальном расстоянии до ближайшего источника;
• BFS сам выберет, от какого источника прийти выгоднее.

Наблюдение 3. Последняя извлечённая клетка

В обычном BFS вершины извлекаются из очереди в порядке неубывания расстояния.
Поэтому одна из клеток, извлечённых последней, будет иметь максимальное расстояние до ближайшего источника.

Значит, можно просто запомнить последнюю обработанную клетку.

3. Алгоритм

1. Считываем размеры поля n, m.
2. Считываем число стартовых клеток k.
3. Создаём массив посещённых клеток.
4. Все стартовые клетки:
   • переводим в индексацию с нуля;
   • помечаем как посещённые;
   • добавляем в очередь BFS.
5. Запускаем BFS:
   • берём клетку из начала очереди;
   • запоминаем её как текущий кандидат в ответ;
   • пробуем перейти в 4 соседние клетки;
   • если сосед внутри поля и ещё не посещён, помечаем его и кладём в очередь.
6. После завершения BFS последняя обработанная клетка — ответ.
7. Выводим её координаты в 1-based формате.

4. Почему это работает

Докажем корректность.

Пусть есть множество стартовых клеток. Рассмотрим BFS, который начинает работу одновременно из всех этих клеток.

Шаг 1. BFS правильно находит расстояния до ближайшего источника

В начале все стартовые клетки находятся в очереди и имеют расстояние 0.
Далее BFS распространяется слоями:

• сначала все клетки на расстоянии 0,
• потом все клетки на расстоянии 1,
• потом на расстоянии 2,
• и так далее.

Это стандартное свойство BFS в невзвешенном графе.

Сетка — это невзвешенный граф, где каждая клетка соединена с соседями по сторонам.
Поэтому для любой клетки BFS найдёт минимальное число шагов до ближайшей стартовой клетки.

Шаг 2. Последняя обработанная клетка имеет максимальное расстояние

Так как BFS обрабатывает клетки в порядке неубывания расстояния, то если клетка обработана позже другой, её расстояние не меньше.

Значит, одна из последних обработанных клеток принадлежит самому дальнему слою, то есть имеет максимальное расстояние до ближайшего источника.

Мы сохраняем последнюю извлечённую из очереди клетку, следовательно, в конце получаем корректный ответ.

Шаг 3. Если ответов несколько

Может существовать несколько клеток с одинаковым максимальным расстоянием.
По условию достаточно вывести любую.
Алгоритм именно такую клетку и выдаёт.

Следовательно, алгоритм корректен.

5. Сложность

Пусть поле содержит n · m клеток.

• Каждая клетка не более одного раза добавляется в очередь.
• Из каждой клетки проверяется до 4 соседей.

Итого:

• время: O(n · m)
• память: O(n · m)

CPP

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<vector<bool>> used(n + 1, vector<bool>(m + 1, false));
    queue<pair<int, int>> q;

    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        if (!used[x][y]) {
            used[x][y] = true;
            q.push({x, y});
        }
    }

    int ansx = 1, ansy = 1;
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        ansx = x;
        ansy = y;

        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !used[nx][ny]) {
                used[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    cout << ansx << ' ' << ansy << '\n';
    return 0;
}

PYTHON

from collections import deque
import sys

def main():
    data = list(map(int, sys.stdin.read().split()))
    if not data:
        return

    n, m, k = data[0], data[1], data[2]
    ptr = 3

    used = [[False] * (m + 1) for _ in range(n + 1)]
    q = deque()

    for _ in range(k):
        x, y = data[ptr], data[ptr + 1]
        ptr += 2
        if not used[x][y]:
            used[x][y] = True
            q.append((x, y))

    ansx, ansy = 1, 1
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    while q:
        x, y = q.popleft()
        ansx, ansy = x, y

        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 1 <= nx <= n and 1 <= ny <= m and not used[nx][ny]:
                used[nx][ny] = True
                q.append((nx, ny))

    print(ansx, ansy)

if __name__ == "__main__":
    main()