Минное поле

Будем поддерживать для каждой клетки ближайшую клетку, в которой еще не выкопана бомба, в каждом из четырех направлений. Когда поступает запрос на нахождение клетки с бомбой, пройдемся по этим переходам в нужном направлении, пока не дойдем до клетки с бомбой или до границы поля. После этого, во всех клетках, по которым мы прошли, обновим ссылку, теперь они будут указывать на клетку, которая сейчас является ответом. Таким образом, получился аналог системы непересекающихся множеств с эвристикой переподвешиваний. Значит, амортизированное время работы — $$$O(\log n)$$$ на запрос.

В первой подгруппе можно было поддерживать клетки с бомбами, и при каждом запросе перебирать клетки в нужном направлении, пока не встретится клетка с бомбой. Асимптотика решения — $$$O(q \cdot (n + m))$$$.

Во второй подгруппе можно было обработать все запросы на выкапывание бомб, а потом с помощью метода динамического программирования найти ближайшую клетку с бомбой для каждой клетки в каждом направлении. Рассмотрим, как найти ближайшую клетку с бомбой для каждой клетки в направлении вверх. Будем перебирать клетки по строкам от верхней до нижней. Для очередной клетки, если соседняя сверху клетка содержит бомбу, она является ближайшей, содержащей бомбу. Иначе, ответ для текущей клетки совпадает с ответом для соседней сверху клетки. Направления вниз, влево и вправо решаются аналогично. Асимптотика решения — $$$O(n \cdot m + q)$$$.