Codeforces Round 919 (Div. 2) |
---|
Закончено |
Единственное отличие двух версий этой задачи состоит в ограничении на $$$q$$$. Вы можете делать взломы, только если обе версии задачи решены.
Томас плавает вокруг острова, окружённого океаном. Океан и остров можно представить в виде таблицы с $$$n$$$ строками и $$$m$$$ столбцами. Строки пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы пронумерованы от $$$1$$$ до $$$m$$$ слева направо. Позицию клетки в строке $$$r$$$ и в столбце $$$c$$$ обозначим как $$$(r, c)$$$. Ниже приведен пример допустимой таблицы.
Существует три типа клеток: остров, океан и подводный вулкан. Клетки, представляющие остров, отмечены символом '#', клетки, представляющие океан, отмечены символом '.', а клетки, представляющие подводный вулкан, отмечены символом 'v'. Гарантируется, что есть хотя бы одна клетка острова и хотя бы одна клетка подводного вулкана. Также гарантируется, что множество всех клеток острова образует единую связную компоненту$$$^{\dagger}$$$, и множество всех клеток океана и подводных вулканов также образует единую связную компоненту. Кроме того, гарантируется, что на краю таблицы (то есть, в строке $$$1$$$, в строке $$$n$$$, в столбце $$$1$$$ и в столбце $$$m$$$) нет клеток острова.
Определим круговой маршрут, проходимый Томасом, начинающийся в клетке $$$(x, y)$$$, как путь, который удовлетворяет следующим условиям:
Безопасность кругового маршрута — это минимальное манхэттенское расстояние$$$^{\ddagger}$$$ от клетки на круговом маршруте до подводного вулкана (обратите внимание, что наличие клеток острова не влияет на это расстояние).
У вас есть $$$q$$$ запросов. Запрос можно представить как $$$(x, y)$$$, и для каждого запроса вы хотите найти максимальную безопасность кругового маршрута, начинающегося в $$$(x, y)$$$. Гарантируется, что $$$(x, y)$$$ является клеткой океана или подводного вулкана.
$$$^{\dagger}$$$Множество клеток образует единую связную компоненту, если из любой клетки этого множества можно добраться до любой другой клетки этого множества, перемещаясь только по клеткам этого множества, каждый раз переходя в клетку с общей стороной.
$$$^{\ddagger}$$$Манхэттенское расстояние между клетками $$$(r_1, c_1)$$$ и $$$(r_2, c_2)$$$ равно $$$|r_1 - r_2| + |c_1 - c_2|$$$.
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$q$$$ ($$$3 \leq n, m \leq 10^5$$$, $$$9 \leq n \cdot m \leq 3 \cdot 10^5$$$, $$$1 \leq q \leq 5$$$) — количество строк и столбцов таблицы и количество запросов.
Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов, описывающих клетки таблицы. Символ '#' обозначает клетку острова, '.' обозначает клетку океана, и 'v' обозначает клетку подводного вулкана.
Гарантируется, что есть хотя бы одна клетка острова и хотя бы одна клетка подводного вулкана. Гарантируется, что множество всех клеток острова образует единую связную компоненту, и множество всех клеток океана и подводных вулканов также образует единую связную компоненту. Также гарантируется, что нет клеток острова на краю таблицы (то есть, в строке $$$1$$$, в строке $$$n$$$, в столбце $$$1$$$ и в столбце $$$m$$$).
Следующие $$$q$$$ строк описывают запросы. Каждая из этих строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$), обозначающие круговой маршрут, начинающийся в $$$(x, y)$$$.
Гарантируется, что $$$(x, y)$$$ является клеткой океана или подводного вулкана.
Для каждого запроса выведите одно целое число — максимальную безопасность кругового маршрута, начинающегося в указанной клетке.
9 9 3 ......... ......... ....###.. ...v#.... ..###.... ...##...v ...##.... ......... v........ 1 1 9 1 5 7
3 0 3
3 3 5 ..v .#. ... 1 2 1 3 2 3 2 1 3 2
0 0 0 0 0
14 13 5 ............. ............. ............. ...vvvvvvv... ...v.....v... ...v.###.v... ...v.#.#.v... ...v..v..v... ...v..v..v... ....v...v.... .....vvv..... ............. ............. ............. 1 1 7 7 5 6 4 10 13 6
3 0 1 0 2
10 11 4 ........... ..#######.. ..#..#..#.. ..#.....#.. ..#..v..#.. ..#.###.#.. ..#.#.#.#.. ..#...#.#.. ..#####.#.. ........... 7 6 3 7 6 8 1 1
1 2 3 4
Для первого примера на изображении ниже показан оптимальный круговой маршрут, начинающийся в $$$(1, 1)$$$. Безопасность кругового маршрута равна $$$3$$$, так как минимальное манхэттенское расстояние от клетки на круговом маршруте до подводного вулкана равно $$$3$$$.
В четвёртом примере помните, что Томасу разрешается посещать одну и ту же клетку несколько раз за один круговой маршрут. Например, это необходимо для кругового маршрута, начинающегося в $$$(7, 6)$$$.
Название |
---|