B. Биридианский лес
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вы — разводчик микемонов. Вы на полпути к званию повелителя микемонов, но вот, Вы сталкиваетесь с проблемой: надо пройти через печально известный Биридианский лес.

Биридианский лес

Биридианский лес представляет собой двухмерную таблицу, состоящую из r строк и c столбцов. Каждая ячейка Биридианского леса может либо быть пустой, либо содержать дерево. В пустой ячейке могут распологаться ноль или больше разводчиков микемонов (кроме вас в лесу могут быть и другие разводчики). Разводчики микемонов (включая Вас) не могут заходить в ячейки с деревьями. Одна из ячеек служит ячейкой выхода.

Вам даны исходная таблица с Вашим начальным положением, ячейка выхода и начальные положения всех остальных разводчиков. Вот пример такой таблицы (из первого тестового примера):

Передвижение

Разводчики (включая Вас) могут двигаться по лесу. За один ход разводчики могут выполнить одно из следующих действий:

  • Ничего не делать.
  • Перейти из текущей ячейки в одну из четырех соседних ячеек (две ячейки называются соседними тогда, когда они имеют общую сторону). Обратите внимание, что разводчики не могут заходить в ячейки с деревьями.
  • Если Вы стоите в ячейке выхода, то можете выходить из леса. Этот ход доступен только Вам — все остальные разводчики микемонов никогда не воспользуются этим шагом для выхода из леса.

После каждого Вашего шага все остальные разводчики одновременно делают ход (каждый из них выбирает ход независимо от других).

Битва микемонов

Если Вы и t (t > 0) разводчиков микемонов оказались в одной ячейке, тут же разгорится ровно t битв микемонов (так как вы будете сражаться с каждым из разводчиков в этой клетке). После сражения, все t разводчиков покинут лес.

Обратите внимание, что после того, как Вы покинете лес, битв микемонов больше быть не может, даже если сразу за Вами в клетку выхода заходит другой разводчик микемонов. Также обратите внимание на то, что битвы проводятся только между Вами и другими разводчиками — между собой остальные разводчики не дерутся (в одной клетке могут находится несколько разводчиков одновременно).

Ваша задача

Вы хотели бы выбраться из леса. Для этого надо совершить некоторую последовательность шагов, завершающуюся шагом финального типа. Однако перед тем, как совершить этот грандиозный поход, вам надо опубликовать всю последовательность в своем виртуальном блоге Идол. Затем можно верно следовать этой последовательности движений.

Задачи других разводчиков

Вы публикуете Вашу последовательность в личном блоге, поэтому остальные разводчики будут в курсе всех Ваших передвижений еще до первого Вашего шага. Каждый из них будет двигаться так, чтобы гарантированно устроить с Вами битву микемонов, если это возможно. Если кто-то из разводчиков не сможет гарантированно устроить с Вами битву микемонов, он не будет ничего делать.

Ваше задание

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

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

В первой строке записано два целых числа: r и c (1 ≤ r, c ≤ 1000), обозначающих количества строк и столбцов в Биридианском лесу. В следующих r строках записано по строке карты, где каждый символ представляет содержимое соответствующей ячейки:

  • 'T': Ячейка, содержащая дерево.
  • 'S': Пустая ячейка и Ваша начальная позиция. Эта ячейка встретится на карте ровно один раз.
  • 'E': Пустая ячейка, содержащая выход. Эта ячейка встретится на карте ровно один раз.
  • Цифра (0-9): Ячейка, содержащая цифру X обозначает, что ячейка пустая и в ней стоят X разводчиков (если X равняется нулю, это значит, что ячейка не занята ни одним разводчиком).

Гарантируется, что Вы можете дойти от начальной позиции до ячейки выхода.

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

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

Примеры
Входные данные
5 7
000E0T3
T0TT0T0
010T0T0
2T0T0T0
0T0S000
Выходные данные
3
Входные данные
1 4
SE23
Выходные данные
2
Примечание

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

С Вами смогут сразиться три разводчика с левой стороны карты — одинокий разводчик может просто стоять на месте, пока Вы не подойдете, а два других разводчика могут двигаться к одинокому и стоять с ним, поджидая Вас. У трех разводчиков справа не будет возможности сразиться с Вами, и они будут стоять на месте.

Для второго примера надо опубликовать следующую последовательность в блоге:

Случается вот что. Сначала надо шагнуть на ячейку вправо.

Затем, два разводчика правее Вас одновременно шагнут навстречу Вам. Остальные три разводчика не могу с Вами сразиться, поэтому не делают ничего.

Вы находитесь в одной клетке с 2 разводчиками, а значит тут же случится 2 битвы микемонов. После этих битв Ваши противники покинут лес.

И наконец, надо сделать еще один шаг и выйти из леса.