#35. Labirintdan qochish
Sizga N×M o'lchamli xarita berilgan. Xaritada . — ochiq yo'l, # — devor. Siz S (boshlang'ich) nuqtadan E (chiqish) nuqtasiga eng kam qadamda yetib borishingiz kerak. Siz faqat tepaga, pastga, o'ngga va chapga yurishingiz mumkin (diagonal yurish mumkin emas). Agar chiqish yo'li bo'lmasa, -1 chiqaring.
Birinchi qatorda ikkita butun son: N va M beriladi.
Keyingi N ta qatorda M tadan belgi (., #, S, E lardan iborat) beriladi.
Bitta butun son — eng kam qadamlar sonini, agar yo'l bo'lmasa -1 ni chiqaring.
1 ≤ N, M ≤ 1000
Xaritada faqat bitta S va bitta E qatnashishi kafolatlanadi.
You are given an N×M grid. In the grid, . represents an open path, and # represents a wall. You need to find the minimum number of steps to reach point E (exit) from point S (start). You can only move up, down, left, and right (diagonal moves are not allowed). If there is no valid path, print -1.
The first line contains two integers: N and M.
The next N lines contain M characters each (consisting of ., #, S, E).
Print a single integer — the minimum number of steps. If there is no path, print -1.
1 ≤ N, M ≤ 1000
It is guaranteed that there is exactly one S and one E in the grid.
Вам дана сетка размером N×M. В сетке . означает открытый путь, а # — стену. Вам нужно найти минимальное количество шагов, чтобы добраться от точки S (старт) до точки E (выход). Вы можете двигаться только вверх, вниз, влево и вправо (двигаться по диагонали нельзя). Если пути не существует, выведите -1.
В первой строке заданы два целых числа: N и M.
В следующих N строках заданы по M символов (состоящих из ., #, S, E).
Выведите одно целое число — минимальное количество шагов. Если пути нет, выведите -1.
1 ≤ N, M ≤ 1000
Гарантируется, что в сетке ровно один символ S и один E.
Sizga N×M o'lchamli xarita berilgan. Xaritada . — ochiq yo'l, # — devor. Siz S (boshlang'ich) nuqtadan E (chiqish) nuqtasiga eng kam qadamda yetib borishingiz kerak. Siz faqat tepaga, pastga, o'ngga va chapga yurishingiz mumkin (diagonal yurish mumkin emas). Agar chiqish yo'li bo'lmasa, -1 chiqaring.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita butun son: N va M beriladi.
Keyingi N ta qatorda M tadan belgi (., #, S, E lardan iborat) beriladi.
Chiquvchi ma'lumotlar
Bitta butun son — eng kam qadamlar sonini, agar yo'l bo'lmasa -1 ni chiqaring.
Cheklovlar
1 ≤ N, M ≤ 1000
Xaritada faqat bitta S va bitta E qatnashishi kafolatlanadi.
Misollar
3 3 S.. ##. E..
4
3 3 S.. ### E..
-1