АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Рон, Хэрмойниа хоёр Нууц ойд хорны жоруудыг хайж яваад төөрчээ.

Ойн гарцууд хаагдсан учраас тэд шидэт хаалгыг олж түүгээр дамжин шууд Хогварц руу шилжин очно.

Ойг n x m нүднүүдтэй талбар гэж үзээд нүд бүр хоосон буюу .  эсвэл модтой буюу X байна.

Рон, Хэрмойниа хоёр хамтдаа нэг нүдэнд зогсож багтах ба тэд хамтдаа зүүн, баруун, дээш, доош алхаж чадна.

Гэхдээ зөвхөн хоосон нүдэн дээр л зогсож чадах ба модтой нүдэн дээр зогсож чадахгүй.

Тэдний анх зогсож байсан нүдийг М–ээр тэмдэглэсэн.

Шидэт хаалгатай нүдийг *-ээр тэмдэглэсэн. Зүүн дээд буланг 0,0-оор тэмдэглэсэн.

.X.X......X

.X*.X.XXX.X

.XX.X.XM...

......XXXX.

Дээрх жишээнд

Рон болон Хэрмойниа хоёр (2, 7) нүдэнд анх зогсож байсан ба шидэт хаалга (1, 2) нүдэнд баярлаж байгаа.

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

Рон Хэрмойниаг яг k удаа дохиураа ашиглана гэж таамаглажээ. Роны зөв байсан эсэхийг ол.

Доор тэдний явсан замыг 0 ба 1-ээр дүрсэлсэн ба 1 байгаа газар бүрт Хэрмойниа шидэт дохиураа ашигласан.

.X.X.10000X

.X*0X0XXX0X

.XX0X0XM01.

...100XXXX.

Тэмдэглэл

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

Функцийн тайлбар

CountLuck гэдэг функцийг бичнэ үү. Хэрвээ Роны зөв бол “Impressed” буруу бол “Oops!” гэж хэвлэнэ үү.

CountLuck доорх өгөгдлийг хүлээн авна.

matrix: string-үүдийн дараалал өгөгдөнө. String тус бүр ойн нэг мөрийг илтгэнэ.

k: Роны тааж хэлсэн тоо

Оролтын бүтэц

Эхний мөрөнд тестийн тоо t өгөгдөнө.

Тест тус бүрийн:

Эхний мөрөнд бүхэл тоо , n , m зайгаар тусгаарлагдан өгөгдөнө. Ойн урт ба өргөн.

Дараагийн n мөрөнд m урттай string өгөгдөнө.

Сүүлийн мөрөнд k тоо өгөгдөх ба энэ нь Роны таамаглал.

Хязгаарлалт

1 <= t <= 10

1 <= n,  m <= 100

1 <= k <= 10,000

Ойд яг нэг ширхэг M ба * өгөгдөнө.

M-ээс * хүртэл яг нэг боломжит зам байна.

Гаралтын бүтэц

Тест тус бүрт нэг мөрөнд хэрвээ Рон-ий зөв бол “Impressed” буруу бол “Oops!” гэж хэвлэнэ үү.

Жишээ

Оролт

3

2 3

*.M

.X.

1

4 11

.X.X......X

.X*.X.XXX.X

.XX.X.XM...

......XXXX.

3

4 11

.X.X......X

.X*.X.XXX.X

.XX.X.XM...

......XXXX.

4

Гаралт

Impressed

Impressed

Oops!

Орчуулсан : Б.Мөнхбаяр АНУ