ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / USACO /

Фермер Жоны толгойд солиотой санаа төрж эдлэн газартаа аварга том төөрдөг байшин барьжээ. Аз болоход гаднах хашаанд хоёр банз дутаж хоёр хаалгатай болжээ. Үүнээс ч сайхан зүйл бол түүний барьсан төөрдөг байшингийн доторх аль ч цэгээс гарц олдох бөгөөд тэрээр үүнийгээ төгс төөрдөг байшин гэж нэрлэжээ.

W (1 <= W <= 38) өргөнтэй H (1 <= H <= 100) өндөртэй, 2*H+1 болон 2*W+1 тэмдэгтээс бүтэх доор үзүүлэх форматаар өгөгдсөн төөрдөг байшин өгөгджээ. Таны даалгавар бол төөрдөг байшингийн доторх хамгийн муу цэгээс ( хамгийн хялбар замаар явахад бусад аль ч хэсгээс явснаас хамгийн их хугацаа зарцуулах) төөрдөг байшингаар гарах хүртэл хэдэн алхам явахыг олох юм. Мэдээж үнээнүүд х, у тэнхлэгтэй паралель буюу перпендикуляраар явах бөгөөд диагональдаж явахгүй. Шинэ нүдэнд шилжих бүрт нэг нэгж зай гэж үзнэ ( төөрдөг байшингаас гарахыг бас нэг шилжилт гэж тооцно).

W=5, H=3 хэмжээтэй төөрдөг байшинг үзүүллээ.

+-+-+-+-+-+

|         |

+-+ +-+ + +

|     | | |

+ +-+-+ + +

| |     | 

+-+ +-+-+-+

Хашааны гадаснууд нь зөвхөн сондгой тоотой мөр болон баганад байрлана (жишээнд байгаа шиг). Төөрдөг байшин гаднах ханандаа яг хоёр ширхэг хоосон хэсэгтэй.

Програмын Нэр: maze1

Оролтын Формат

Жишээ Ололт (файл maze1.in)

5 3

+-+-+-+-+-+

|         |

+-+ +-+ + +

|     | | |

+ +-+-+ + +

| |     | 

+-+ +-+-+-+

Гаралын Формат

Нэг бүхэл тоо  байна. Төөрдөг байшингийн аль ч цэгээс үнээний найдвартай гарч чадах хамгийн бага алхамын тоо.

Жишээ Гаралт (файл maze1.out)

9

Тайлбар: Зүүн доод булангаас гарахад хамгийн багадаа 9 алхам.

Орчуулсан : Б.Даваабаяр