eolymp
Məsələlər

Li Çakın intiqamı

Li Çakın intiqamı

prb88

“Mən dəniz qulduru olmaq istəyirəm!” Biz Monkey Island ("Meymunlar adası") kompyuter oyunları seriyasında Qaybraş Tripvudun bu məşhur frazasını xatırlayırıq. Qaybraş indi digər bir macərada iştirak edir və bu dəfə məsələ ölüm-dirim məsələsi olduğuna görə onun Sizin ciddi köməyinizə ehtiyacı var.

Bizim Qaybraş daha sirli bir xəzinə haqqında yerində nə isə öyrənmək məqsədilə sonuncu macərasında sirli adaya (TO) üzdü. Həmin vaxt Li Çak gedişdən xəbər tutdu və sirli adada (TO) ona tələ hazırladı. TO düzbucaqlı formasındadır (hər halda biz bilirik ki, o sirlidir) və onun xəritəsinə həmin ölçülü matris kimi baxıl bilər. Bu matrisin hər bir elementini məntəqə adlandıraq. Bəzi məntəqələr dağ qayalıqları ilə örtülü ola bilər. Belə məntəqələr keçilməz məntəqələr adlanır.

Xəritəsi şəkildə verilmiş adaya baxaq. Bu xəritə 6 sətir və 7 sütundan ibarət bir matris kimi təsvir olunmuşdur. “R” otaqları qayalıqlı məntəqələri göstərir. Qaybraş “g” ilə qeyd edilmiş məntəqədən, Li Çak isə “I” məntəqəsindən başlamalıdır. Əgər Qaybraş xəritədə “e” ilə işarələnmiş son məntəqəyə çata bilərsə, onun bu lənətlənmiş adadan qaçmaq imkanı var. Hər vahid zamanda Qaybraş cari məntəqədən şaquli və ya üfüqi (diaqonal üzrə deyil) qonşu məntəqəyə, əgər onda qayalıqlar yoxdursa keçə bilər və ya hərəkət etməz. Başqa sözlə, o bir məntəqə yuxarı, aşağı, sola, sağa yer dəyişə bilər və ya ümumiyyətlə yerində qalar. Göstərilən nümunədə Qaybraş, ilk anlarda yerində qala bilər və ya özündən sol tərəfdəki otağa keçə bilər. Bütün göstərilən qaydalar Li Çakın hərəkətinə də tətbiq edilir, lakin bir fərqlə: o, sonuncu məntəqəyə (“e” ilə işarələnmiş) keçə bilməz. Başqa sözlə, hər vahid vaxtda Li Çak bir məntəqə(əgər yalnız bu məntəqə “R” və ya “e” deyilsə) yuxarı, aşağı, sola, sağa hərəkət edə bilər və ya dayanar. Biz belə fərz edirik ki, hər vahid vaxtda əvvəlcə Qaybraş gediş edir (və ya dayanır), sonra Li Çak gedir (yə ya dayanır), sonrakı vahid vaxtda yenə əvvəlcə Qaybraş, sonra Li Çak gedir və s. Əgər Qaybraş və Li Çak eyni bir məntəqədə görüşərlərsə, onda Li Çak bizim bədbəxt Qaybraşı ləngimədən öldürər.

Sizin tapşırığınız bundan ibarətdir ki, heç olmasa bir təhlükəsiz yolun olub-olmadığını öyrənəsiniz. Təhlükəsiz yol- Qaybraş üçün elə yoldur ki ( “g”-dən “e”-yə), Li Çakın hər vahid vaxtda nə etməsindən asılı olmayaraq Qaybraşı bu yolda tuta bilmir. Məsələn, göstərilən xəritədə “Sola, Yuxarı, Yuxarı, Yuxarı, Sağa”( 5 vahid vaxtda) ardıcıllığı təhlükəsiz yoldur, çünki Li Çak bu 5 vaxt vahidində Qaybraşı tuta bilmir.

Giriş verilənləri

Girişin 1-ci sətrində yeganə tam ədəd-test hallarının sayı yerləşir. Sonra test halları üçün məlumatlar olan sətirlər gəlir. Hər bir test sirli xəzinənin xəritəsində sətir və sütunların sayını göstərən iki tam RC (4 <= R, C <= 30) ədəd olan sətirlə başlayır. Daha sonra hər birində xəritəni təsvir edən C sayda simvol olan R sayda sətir gəlir. Xəritədə "g", "l" və "e" işarəli bir qeydlər var.

İlkin qayalıqsız boş məntəqələr boşluq simvolu ilə işarələnmişdir. Xəritənin hər hansı sərhəddində yerləşən bütün məntəqələr qayalıqla doldurulmuşdur.

Çıxış verilənləri

Hər bir test üçün yeganə sətir verilir. Əgər test halı üçün heç olmasa bir təhlükəsiz yol varsa, çıxışa "YES" sözü, belə yol yoxdursa "NO" sözü verilməlidir. Fərz edilir ki, təhlükəsiz yol var, lakin Qaybraşın bu yolu getməsi üçün ona 1000 vaxt vahidindən çox olmayan vaxt lazımdır.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #2
1
6 7
RRRRRRR
R e   R
R     R
R RRR R
R gRl R
RRRRRRR
Çıxış verilənləri #2
YES