Муниципальная олимпиада 2024, 7-8 кл.

Задача C. Карта вселенной ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Входной файл:	Стандартный вход	Ограничение времени:	1 сек
Выходной файл:	Стандартный выход	Ограничение памяти:	256 Мб
Максимальный балл:	100

Условие

Астроном Кирилл изучает космос с помощью гигантского телескопа. Кирилл собрал кучу данных и скомпилировал их в одно гигантское изображение (карту вселенной) размером N*M, где N — размер карты по вертикали, а M — размер карты по горизонтали. Изображение включает пустое пространство "." и галактики "#". Например:

0	1	2	3	4	5
1	.	.	.	.	.
2	#	.	.	.	#
3	.	.	.	.	.
4	.	.	.	#	.
5	.	.	#	.	.

Кирилл пытается вычислить сумму длин кратчайшего пути между каждой парой галактик. Но есть одна загвоздка: за то время, пока создавалась карта, вселенная расширилась.Из-за чего-то связанного с гравитацией, расширилась только часть космического пространства. Кириллу стало известно, что на его карте любые строки или столбцы, которые не содержат галактик, на самом деле должны быть в 3 раза больше.

Вычислив как на самом деле должна выглядеть карта Кирилла, можно найти кратчайшие пути между каждой парой галактик. Каждую пару считайте только один раз. Для каждой пары найдите любой кратчайший путь между двумя галактиками. Передвижение из любого места на карте возможно только вверх, вниз, вправо и влево и только по одной "." или "#" за раз. Двигаться по диагонали нельзя. Возможна ситуация, когда кратчайший путь будет идти сквозь другую галактику "#".

По полученной карте найдите длину кратчайшего пути между каждой парой галактик с учётом расширения вселенной. Какова сумма этих длин?

Формат входных данных

В первой строке вводятся целые числа N и M — размеры карты, составленной Кириллом (2 ≤ N, M ≤ 25). Ниже идут M строк, состоящих из N символов "." или "#" — исходная карта вселенной.

2 ≤ число галактик ≤ 50

Формат выходных данных

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

Примечание

В приведённом выше примере один столбец и две строки не содержат галактик:

		↓
→	.	.	.	.	.	←
	#	.	.	.	#
→	.	.	.	.	.	←
	.	.	.	#	.
	.	.	#	.	.
		↑

Эти строки и столбцы должны быть втрое больше. Соответственно исправленная карта выглядит следующим образом:

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	#	.	.	.	.	.	#
5	.	.	.	.	.	.	.
6	.	.	.	.	.	.	.
7	.	.	.	.	.	.	.
8	.	.	.	.	.	#	.
9	.	.	.	.	#	.	.

Получив корректную карту, можно найти кратчайший путь между каждой парой галактик. В примере выше 4 галактики образуют 6 пар. Для большей наглядности пронумеруем галактики. Например, вот один из кратчайших путей "+" между галактикой 1 и 4:

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	1	+	.	.	.	.	2
5	.	+	.	.	.	.	.
6	.	+	+	.	.	.	.
7	.	.	+	+	.	.	.
8	.	.	.	+	+	3	.
9	.	.	.	.	4	.	.

Этот путь имеет длину 9, поскольку требуется минимум 9 шагов, чтобы добраться от галактики 1 до галактики 4 (восемь отмеченных мест "+" плюс шаг в саму галактику 4). Вот ещё несколько кратчайших путей:

--- Между галактикой 1 и галактикой 2: 6

--- Между галактикой 4 и галактикой 3: 2

Примеры тестов

№	Стандартный вход	Стандартный выход
1	`5 5 ..... #...# ..... ...#. ..#..`	`38`

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	#	.	.	.	.	.	#
5	.	.	.	.	.	.	.
6	.	.	.	.	.	.	.
7	.	.	.	.	.	.	.
8	.	.	.	.	.	#	.
9	.	.	.	.	#	.	.

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	1	+	.	.	.	.	2
5	.	+	.	.	.	.	.
6	.	+	+	.	.	.	.
7	.	.	+	+	.	.	.
8	.	.	.	+	+	3	.
9	.	.	.	.	4	.	.

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	#	.	.	.	.	.	#
5	.	.	.	.	.	.	.
6	.	.	.	.	.	.	.
7	.	.	.	.	.	.	.
8	.	.	.	.	.	#	.
9	.	.	.	.	#	.	.

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	1	+	.	.	.	.	2
5	.	+	.	.	.	.	.
6	.	+	+	.	.	.	.
7	.	.	+	+	.	.	.
8	.	.	.	+	+	3	.
9	.	.	.	.	4	.	.

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	#	.	.	.	.	.	#
5	.	.	.	.	.	.	.
6	.	.	.	.	.	.	.
7	.	.	.	.	.	.	.
8	.	.	.	.	.	#	.
9	.	.	.	.	#	.	.

0	1	2	3	4	5	6	7
1	.	.	.	.	.	.	.
2	.	.	.	.	.	.	.
3	.	.	.	.	.	.	.
4	1	+	.	.	.	.	2
5	.	+	.	.	.	.	.
6	.	+	+	.	.	.	.
7	.	.	+	+	.	.	.
8	.	.	.	+	+	3	.
9	.	.	.	.	4	.	.