1. Идея

Сигнал распространяется по клетчатому полю по соседям вверх, вниз, влево и вправо. Если в нескольких кварталах тревога началась одновременно, то естественно рассматривать распространение сигнала сразу из всех этих клеток.

Это классическая задача на поиск кратчайших расстояний в невзвешенном графе. Каждая клетка сетки — вершина, переход в соседнюю клетку — ребро длины 1.

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

Главная идея решения:

• положить все стартовые клетки в очередь сразу;
• запустить обычный BFS;
• последняя извлечённая из очереди клетка и будет одной из самых дальних.

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

Наблюдение 1. BFS в невзвешенном графе находит кратчайшие расстояния

Если из одной вершины сделать BFS, то вершины будут посещаться в порядке неубывания расстояния от старта.

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

Наблюдение 2. Последняя обработанная клетка — одна из самых дальних

Так как BFS идёт слоями:

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

то в конце очереди окажутся клетки с максимальным возможным расстоянием до ближайшего старта.

Значит, достаточно во время BFS запоминать текущую извлечённую из очереди клетку. Когда обход закончится, последняя такая клетка и будет ответом.

Наблюдение 3. Явно хранить расстояния не обязательно

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

Поэтому можно хранить только массив посещённости used и очередь BFS. Это экономит память и упрощает код.

Наблюдение 4. Повторяющиеся стартовые клетки возможны

Хотя обычно стартовые позиции задаются корректно, в эталонном решении есть защита от повторов: если одна и та же клетка встречается несколько раз, она добавляется в очередь только один раз.

Это правильно и безопасно.

3. Алгоритм

1. Считать N, M, K.
2. Создать массив used размера N x M, изначально заполненный false.
3. Создать очередь.
4. Для каждой из K стартовых клеток:
   • перевести координаты в индексацию с нуля;
   • если клетка ещё не отмечена:
     • пометить её как посещённую;
     • добавить в очередь.
5. Пока очередь не пуста:
   • извлечь клетку (x, y) из начала очереди;
   • запомнить её как текущий ответ;
   • попробовать перейти в 4 соседние клетки;
   • если сосед внутри поля и ещё не посещён:
     • пометить его;
     • добавить в очередь.
6. После завершения BFS вывести последнюю запомненную клетку, переведя координаты обратно в индексацию с единицы.

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

Рассмотрим граф, где:

• каждая клетка сетки — вершина;
• между двумя соседними по стороне клетками есть ребро.

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

Если тревога начинается сразу в нескольких клетках, то для любой клетки города интересует минимальное расстояние до любого стартового квартала.

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

Почему можно взять именно последнюю извлечённую из очереди клетку?

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

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

5. Сложность

Пусть всего клеток N * M.

Каждая клетка:

• не более одного раза попадает в очередь,
• не более одного раза извлекается из очереди,
• для неё проверяются 4 соседа.

Поэтому:

• время работы: O(N * M)
• память: O(N * M)

Это подходит для ограничений до 2000 x 2000.

6. Код на C++17

#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<char>> used(n, vector<char>(m, 0));
    queue<pair<int, int>> q;

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

    int ansx = 0, ansy = 0;
    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 >= 0 && nx < n && ny >= 0 && ny < m && !used[nx][ny]) {
                used[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }

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

7. Код на Python 3

import sys
from collections import deque

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

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

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

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

    ansx = ansy = 0
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

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

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

    sys.stdout.write(f"{ansx + 1} {ansy + 1}\n")

if __name__ == "__main__":
    main()