C. Уралдааны зам

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

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

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

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

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

Уралдааны замын газрын зураг нь нүднүүдэд хуваагдсан $n × m$ хэмжээтэй тэгш өнцөгтөөр дүрслэгдэнэ. Тэгш өнцөгтийн нүд болгон нь Латин жижиг үсгээр тэмдэглэгдсэн байх бөгөөд эдгээр нь уг нүдний төрлийг илэрхийлэх юм. Гэхдээ зөвхөн уралдааны гарааны нүд (уг нүд нь Латин том $S$ үсгээр тэмдэглэгдсэн байна) болон барианы нүд (уг нүд нь Латин том $T$ үсгээр тэмдэглэгдсэн байна) нь бусад нүднүүдээсээ өөрөөр тэмдэглэгдсэн байх юм. Нэг нүднээс өөр нэгэн нүд уруу шилжих хугацаа нь $1$ минут гэж үзэх ба нүд дотор хөдлөх хугацааг тооцохгүй. Бид ямар нэгэн нүднээс уг нүдтэй хөрш талтай нүд уруу шилжиж болох боловч уралдааны замын газрын зургаас гадагш гарах нь хориглогдсон байв. Түүнчлэн уралдааны замд дараах шаардлага тавигдсан байв: уралдааны замын турш $k$-аас их төрлийн ялгаатай нүднүүдээр зорчих нь зөвшөөрөгдөөгүй байв. Бид $S$ болон $T$ гэж тэмдэглэгдсэн нүднүүдийг ямар нэгэн төрөлгүй гэж үзэх учраас тэдгээрийг тоолохгүй. Гэвч $S$ гэж тэмдэглэгдсэн нүдээр яг нэг удаа зорчих бөгөөд тодруулбал хамгийн эхэнд зорчих юм. Харин $T$ гэж тэмдэглэгдсэн нүдээр яг нэг удаа зорчих бөгөөд тодруулбал хамгийн сүүлд зорчих юм.

Таны даалгавар бол $S$ нүднээс $T$ нүд хүртэлх хамгийн бага хугацаа зарцуулах замыг олох юм. Та хамгийн богино урттай бүх замууд дундаас хэл зүйн хувьд хамгийн бага нэгийг нь сонгох ёстой. Та тэдгээр замуудыг хэл зүйн хувьд харьцуулж байхдаа тэмдэгтүүдийн дараалал хэлбэртэй бичиж харьцуулна. Өөрөөр хэлбэл замуудыг тухайн нүднүүдийн төрлүүдийн дараалал хэлбэрээр бичиж дараа нь хэл зүйн харьцуулалт хийх юм.

Оролт

Эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $k$ ($1 ≤ n, m ≤ 50, n*m ≥ 2, 1 ≤ k ≤ 4$) өгөгдөнө. Дараагийн $n$ мөрөнд уралдааны замын газрын зураг өгөгдөнө. Мөр болгон нь яг $m$ ширхэг тэмдэгт бүхий урттай байх бөгөөд Латин жижиг үсгүүд, $S$ болон $T$ гэсэн тэмдэгтүүд агуулсан байна. Мөн газрын зураг нь яг нэг ширхэг $S$, яг нэг ширхэг $T$ гэсэн тэмдэгт агуулсан байна.

12-р жишээ тест нь уг бодлогын хамгийн том тестүүдийн нэг нь байх юм.

Гаралт

Хэрэв нөхцөлийг хангах зам оршин байвал, уг замыг нүднүүдийн төрлийн дараалал буюу Латин жижиг үсгүүдийн дараалал хэлбэрээр хэвлэнэ үү. Бусад тохиолдолд "-1" (хашилтгүйгээр) гэж хэвлэнэ үү. Та $S$ тэмдэгтийг эхэнд, $T$ тэмдэгтийг төгсгөлд нь хэвлэх хэрэггүй.

Мөн уг дараалал нь хоосон байж болохыг анхаарна уу. Ийм тохиолдол жишээ тестүүдэд өгөгдсөн байх бөгөөд та юу ч хэвлэхгүй байж болно эсвэл "End of line" гэсэн нэг тэмдэгт мөрийг хэвлэж болох юм. Эдгээрийн аль ч байдлаар хэвлэсэн зөвөөр тооцно.

Орчуулсан: Баатархүү

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

Оролт
5 3 2
Sba
ccc
aac
ccc
abT
Гаралт
bcccc
Оролт
3 4 1
Sxyy
yxxx
yyyT
Гаралт
xxxx
Оролт
1 3 3
TyS
Гаралт
y
Оролт
1 4 1
SxyT
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...