Đường ngắn nhất trong mê cung

Trung bình

đồ thịBFSlưới5 test · 3 giây

Mê cung n × m gồm . (đường đi), # (tường), một ô S (xuất phát) và một ô E (đích). Mỗi bước đi sang ô kề cạnh (4 hướng). Cần ít nhất bao nhiêu bước để từ S tới E? Nếu không tới được, in -1.

Mọi bước có cùng chi phí → BFS cho đường ngắn nhất.

Dữ liệu vào

Dòng 1: n m (1 ≤ n, m ≤ 1000, n·m ≥ 2).

n dòng, mỗi dòng m ký tự.

Dữ liệu ra

Số bước ít nhất, hoặc -1.

Ví dụ

Input

4 5
S.#..
.##.#
...#E
.#...

Output

Input

2 2
S#
#E

Output

-1

Bài tiếp theo: Đếm thành phần liên thông →

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.