e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.

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

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

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

prb6426

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

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

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

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

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
5 9
****#****
*..#.#..*
****.****
*$#.#.#$*
*********
5 11
*#*********
*$*...*...*
*$*.*.*.*.*
*...*...*.*
*********.*
9 9
*#**#**#*
*#**#**#*
*#**#**#*
*#**.**#*
*#*#.#*#*
*$##*##$*
*#*****#*
*.#.#.#.*
*********
Вихідні дані #1
4
0
9
Джерело 2013 Benelux Algorithm Programming Contest (BAPC )