Labirint

Qiyin 2 s 256 MB1 kishi yechgan

$n \times m$ o‘lchamli labirint berilgan: . — bo‘sh katak, # — devor, S — boshlang‘ich nuqta, E — chiqish. Har qadamda yuqoriga, pastga, chapga yoki o‘ngga qo‘shni bo‘sh katakka o‘tish mumkin.

S dan E gacha eng kam qadamlar sonini toping.

Kiritish

Birinchi qatorda $n$ va $m$ ( $1 \le n, m \le 1000$ ). Keyingi $n$ qatorda $m$ tadan belgi. S va E aniq bir martadan uchraydi.

Chiqarish

Eng kam qadamlar soni. Chiqishga yetib bo‘lmasa, -1.

Namunalar

Kiritish 1

3 4
S..#
.#..
...E

Chiqarish 1

Kiritish 2

2 2
S#
#E

Chiqarish 2

-1

Manba: NolbirKod namuna