e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin
Yarışlar

0-1 BFS

Сломать тюрьму

Миссия Джона состоит в том, чтобы вытащить двух человек из тюрьмы. Тюрьма представляет собой одноэтажное здание. Джон сумел достать подробный план этажа с указанием всех стен и дверей. Он также знает расположение двух людей, которых должен освободить. Тюремные охранники не проблема - он спланировал диверсию, в результате которой они покинут здание практически незаметно.

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

prb6426

Входные данные

Первая строка содержит количество тестов, не более 100. Каждый тест содержит:

  • одна строка содержит два числа h и w (2h, w100): ширину и высоту карты.
  • h строк по w символов описывающих здание тюрьмы:
  • '.' пустое место.
  • '*' непроницаемая стена.
  • '#' дверь.
  • '$' один из двух людей которых следует освободить.

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

Выходные данные

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********
Çıxış verilənləri #1
4
0
9
Mənbə 2013 Benelux Algorithm Programming Contest (BAPC )