PROGRAMING PROBLEMS

Төгөлдөр Тэмүүлэн хоёр шинэ хөлөгт тоглоомтой болжээ. Тоглоомын хөлөг нь гүйцэт төгсгөлгүй хоёртын модтой төсөөтэй юм. Тодруулбал тоглоомын хөлөг нь зангилаанууд болон тэдгээрийг холбосон замуудаас бүрдэнэ. Үндэс болох зангилаа нь хөлгийн дээд хэсэгт байрлах бөгөөд түүнийг тэг түвшинд байна гэж үзнэ. Зангилаа бүр эцэг зангилааны зүүн доод ба баруун доод чиглэлд байрлах зүүн ба баруун хүү гэсэн яг хоёр хүү зангилаатай.  Хүү зангилааны түвшин нь эцэг зангилааны түвшингээс нэгээр их байна. Эцэг зангилааг хүү зангилаануудтай холбосон замуудаас гадна бүх зангилаануудыг ижил түвшинд холбосон замууд байдаг. Түвшин бүрийн хувьд хамгийн зүүн зангилаанаас эхлэн зангилаа бүрийг дараагийн зангилааруу баруун тийш холбосон зам байдаг.

Тоглоомын хөлөг дээрх зам бүр нь нэг зангилаанаас өөр нэг зангилааруу шилжих алхмуудын дараалал байна. Алхам бүрийг нэг тэмдэгтээр дараах байдлаар тодорхойлж болно.

• "1" тэмдэгт нь ямар нэг зангилаанаас түүний зүүн хүү зангилааруу шилжих,
• "2" тэмдэгт нь ямар нэг зангилаанаас түүний баруун хүү зангилааруу шилжих,
• "U" тэмдэгт нь ямар нэг зангилаанаас түүний эцэг зангилааруу шилжих,
• "L" тэмдэгт нь ямар нэг зангилаанаас түүнтэй ижил түвшний зүүн зангилааруу шилжих,
• "R" тэмдэгт нь ямар нэг зангилаанаас түүнтэй ижил түвшний баруун зангилааруу шилжих.

Жишээлбэл хэрэв бид үндэс зангилаанаас эхэлж “221LU” алхмуудыг хийвэл дээрх зурагт үзүүлсэн  “A” үсгээр тэмдэглэгдсэн зангилаа руу очих болно.

Даалгавар:

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

Оролт:

Оролтын эхний мөрөнд нь хамгийн ихдээ 100000 тэмдэгтээс бүрдэх дараалал байх бөгөөд энэ нь үндэс зангилаанаас эхний зангилаа хүрэх зам.

Оролтын хоёр дахь мөрөнд нь хамгийн ихдээ 100000 тэмдэгтээс бүрдэх дараалал байх бөгөөд энэ нь үндэс зангилаанаас хоёрдугаар зангилаа хүрэх замыг заана.

Хоёр зам хүчинтэй байх болно (алхам бүрийг хоёр дарааллаар хийх боломжтой болно).

Гаралт:

Өгсөн 2 зангилаа хооронд шилжих хамгийн цөөн алхмын тоо болох нэг бүхэл тоо хэвлэгдэнэ.

Үнэлгээ:

Өгөгдсөн хоёр зам хоёулаа хамгийн ихдээ D түвшинтэй зангилаанууд дээр очдог байхаар хамгийн бага бүхэл тоо D байг.

• Нийт 20 оноотой тестийн тохиолдлуудад D хамгийн ихдээ 10 байна.
• Нийт 40 оноотой тестийн тохиолдлуудад D хамгийн ихдээ 50 байна.
• Нийт 70 оноотой тестийн тохиолдлуудад D хамгийн ихдээ 1000 байна.

Жишээ: