Problem
Melone mahu menguji perkembangan baharunya - robot yang boleh bergerak melalui labirin.
Robot itu berada dalam maze segi empat tepat bersaiz n × m. Setiap sel labirin sama ada kosong atau diduduki oleh halangan.
Robot boleh bergerak antara sel bersebelahan ke kiri (simbol "L"), kanan (simbol "R", atas (simbol "U") atau bawah (simbol "D"). Robot hanya boleh bergerak ke sel jika ia kosong. Pada mulanya, robot itu berada dalam sangkar kosong.
Melone mahu robot itu melalui kitaran minimum leksikografik panjang tepat k, yang bermula dan berakhir dalam sel di mana robot itu berada pada mulanya. Robot dibenarkan melawat mana-mana sel beberapa kali (termasuk yang mula).
Laluan robot diberikan oleh rentetan yang terdiri daripada aksara "L", "R", "U" dan "D". Contohnya, jika robot mula-mula turun, kemudian kiri, kemudian kanan dan atas, maka laluannya ditulis sebagai "DLRU".
Bantu Melona menentukan laluan robot yang sepadan dengan kitaran minimum leksikografik panjang tepat k, atau beritahu saya bahawa tiada perkara sedemikian.
Input:
Baris pertama diikuti oleh tiga integer n, m dan k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 10
6< / sup>) — dimensi labirin dan panjang kitaran.
Setiap satu daripada n baris seterusnya mengandungi m aksara — penerangan tentang labirin. Jika simbol ialah ".", maka sel semasa kosong. Jika simbol ialah "*", maka sel semasa diduduki oleh halangan. Jika simbol itu sama dengan "X", maka pada mulanya robot berada dalam sel ini, dan ia kosong. Ia dijamin bahawa watak "X" berlaku tepat sekali dalam mez.
Output:
Cetak laluan minimum leksikografik Robot dengan panjang tepat k, yang bermula dan berakhir dalam sel di mana Robot berada pada mulanya. Jika tiada laluan sedemikian wujud, cetak "MUSTAHIL" (tanpa petikan).
Contoh:
| Input |
Output |
2 3 2
.**
X.. |
RL |
5 6 14
..***.
*...X.
..*...
..*.**
....*. |
DLDDLLLRRRUURU |
3 3 4
***
*X*
*** |
MUSTAHIL |