ЗАДАЧА G
Кратчайший путь с телепортами
| Имя входного файла: | teleport.in |
| Имя выходного файла: | teleport.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
На прямоугольной доске N на M клеточек, часть клеток - телепорты. Верхний левый угол -- клеточка с координатами (1,1). В клеточке с координатами (x1,y1) находится «сказочный герой», который желает как можно быстрее попасть в клеточку с координатами (x2,y2). За одну секунду герой может либо переместиться в соседнюю клетку, т.е. клетку, имеющую общую сторону с той, в которой он находится, либо, если в текущей клетке есть телепорт, мгновенно (т.е. за 0 секунд) телепортироваться в любой другой телепорт.
Напишите программу, которая найдёт кратчайший по времени путь из клеточки с координатами (x1,y1) в клеточку с координатами (x2,y2).
Входные данные
В первой строке входного файла записаны два числа N (1<=N<=1000) - количество клеточек по вертикали, M (1<=M<=1000) - количество клеточек по горизонтали. В следующих N строках, в каждой по M символов записана доска. Буква “T” - обозначает телепорт, “.” - обозначает обычную клетку. В следующей строке записаны числа x1, y1, x2, y2.Выходные данные
В выходной файл выведите единственное число -- минимальное время, за которое «сказочный герой»может попасть из клеточки (x1,y1) в клеточку (x2,y2).
Пример
| teleport.in | teleport.out |
|---|---|
|
|