Mağara

Gnom Torin, dağ kralı Norusun yaşadığı tərk edilmiş mağaranın xəritəsini tapdı. Xəritədə böyük bir xəzinənin yeri göstərilib. Dağ kralı xəzinəsini axtaranlardan qorumaq üçün mağarada $\text{L}$ daş blokları yerləşdirib. Bu bloklar hərəkət edir və axtaranı əzə bilər, lakin xəzinə tapıldıqda dayanır.

Xəritə tam ədədlərdən ibarət \textbf{M} \times \textbf{N} ölçülü düzbucaqlı matris şəklində təqdim olunur. Elementlər aşağıdakı kimi ola bilər: $\text{-2}$ (xəzinə), $\text{-1}$ (divar), $\text{0}$ (boş yer), müsbət ədəd $\text{K}$ ($\text{K}$-cı blokun elementi). $\text{K}$-cı blok, $\text{K}$ rəqəmi ilə işarələnmiş bütün elementlərdən ibarətdir. Bloklar mütləq əlaqəli deyil, lakin bütün elementləri sinxron şəkildə hərəkət edir. Matrisin kənar sətir və sütunlarındakı sıfırlar mağaraya girişləri göstərir. Hər blokun başlanğıc hərəkət istiqaməti ayrıca verilir ($\text{1}$ — yuxarı, $\text{2}$ — sağa, $\text{3}$ — aşağı, $\text{4}$ — sola).

Gnom giriş hüceyrəsində dayanır. Bundan sonra o, aşağıdakı qaydalara uyğun hərəkət edir: hər saniyə əvvəlcə gnom $4$ qonşu boş hüceyrəyə (yuxarı, aşağı, sola və ya sağa) hərəkət edir və ya yerində qalır. Sonra, həmin saniyə ərzində hər bir blok bir hüceyrə hərəkət edir (yuxarı, aşağı, sola və ya sağa): əvvəlcə birinci, sonra ikinci və s. Əgər hər hansı bir elementin hərəkət istiqamətində divar, mağaranın kənarı, xəzinə və ya başqa bir blok varsa, bu gedişdə blok hərəkət etmir və hərəkət istiqaməti əksinə dəyişir. Əgər blok hərəkət zamanı gnomun olduğu hüceyrəyə düşərsə, gnom ölür.

Xəzinəyə ən qısa zamanda təhlükəsiz bir yol tapmaq üçün CAVE proqramını yazın, belə bir yolun mövcud olduğunu nəzərə alaraq.