AL10-3. Labirint

Labirint n × m kataklardan iborat: . — yo‘lak, # — devor, S — kirish, E — chiqish. Bir qadamda qo‘shni katakka (yuqori, past, chap, o‘ng) o‘tiladi. Kirishdan chiqishgacha eng kamida nechta qadam? Yo‘l bo‘lmasa -1.

Kataklar — graf uchlari, qo‘shnilik — qirralar. BFS.

Kirish ma’lumotlari

Birinchi qatorda n m, keyingi n qatorda labirint.

Chiqish ma’lumotlari

Qadamlar soni yoki -1.

Cheklovlar

1 ≤ n, m ≤ 1000; S va E bittadan.