D. Могой

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

"Могой" (snake, boa, python, worm) хэмээх нэртэй нэгэн нэлээд алдартай тоглоомын дүрмийг санацгаая!

Тоглоом $n × m$ хэмжээтэй тэгш өнцөгт талбайд өрнөнө. Талбайн зарим дөрвөлжин нь явах боломжгүй хана бол үлдсэн дөрвөлжингүүд нь явж сул газар юм.

Та могойг удирдах ба могойн бие нь олон хэсгээс бүтнэ. Хэсэг бүр талбайн сул газрын нэг дөрвөлжинг эзлэх ба нэг сул дөрвөлжинд могойн биеийн нэг л хэсэг байх ёстой. Бүх хэсгүүд $1$-ээс $k$ хүртэл дугаарлагдах ба $k$ нь могойн урт юм. $1$-р хэсэг могойн толгой ба $k$-р хэсэг нь сүүл. Ямар ч $i$ ($1 ≤ i < k$) хэсгийн хувьд $i$ болон $i+1$ дугаартай хэсгүүд хөрш дөрвөлжинд байрлана.

Сул газруудын нэг нь алим агуулна. Могойн зорилго бол алиманд хүрч алимыг идэх (толгойны байршил алимтай дөрвөлжингийн байрлалтай давхцах) юм.

Могой тоглолтын турш хөдөлнө. Нэг хөдлөлтөөр могой толгойгоо хөрш дөрвөлжин рүү зөөж чадна. Биеийн бусад бүх хэсэг толгойг дагана. $i$ $(1 < i ≤ k)$ дугаартай хэсэг бүр $(i-1)$-р хэсгийн байсан нүдэнд очно. Толгойг оролцуулаад бүх хэсэг нэгэн зэрэг хөдлөнө (хоёрдугаар жишээг харна уу). Хэрвээ могойн толгой явах боломжгүй нүд эсвэл өөрийн биеийн аль нэг хэсэг дээр ирвэл могой үхэх учир бид энэ хөдөлгөөнийг тооцохгүй.

Могой алиманд хүрэхийн тулд хамгийн цөөндөө хэдэн нүүдэл хийх шаардлагатайг олно уу.

Оролт

Эхний мөрөнд тоглоомын талбайн мөр ба баганыг тодорхойлох $n$, $m$ тоонууд зайгаар тусгаарлагдан өгөгдөнө. $(1 ≤ n, m ≤ 15)$

Дараагийн $n$ мөрүүд тоглоомын талбарыг тодорхойлно. Мөр бүр $m$ ширхэг тэмдэгт байна. "#" тэмдэгт ханыг илэрхийлэх бол "." тэмдэгт сул нүдийг харин "@" нь алим юм. Могойн эхний хэсэг "1" тэмдэгтээр илэрхийлэгдэх бол хоёр дахь хэрчим нь "2" тэмдэгтээр гэх мэт үргэлжилнэ.

Тоглоомын талбарын тодорхойлолт нь тоо ($0$-ээс бусад) болон "#", ".", "@" тэмдэгтүүдээс өөр тэмдэгт агуулахгүй. Тоглоомын талбай нь нэг могой болон нэг алимтай байх ба могойны урт хамгийн багадаа $3$ ихдээ $9$ байх ёстой.

Гаралт

Могой алиманд хүрэхийн тулд хийх үйлдлийн тоог хэвлэнэ үү. Хэрвээ могой алиманд хүрэх боломжгүй бол "-1" гэж хэвлэнэ үү.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4 5
##...
..1#@
432#.
...#.
Гаралт
4
Оролт
4 4
#78#
.612
.543
[email protected]
Гаралт
6
Оролт
3 2
[email protected]
2#
1#
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...