Bessinin Yuxusu#11162
Farmer Consun-un inəyi Bessi mətbəxdə həddindən artıq çox meyvə yedikdən sonra ona çox qəribə yuxular görünməyə başladı! Ən son yuxusunda o, n \times m ölçülü plitələr şəbəkəsi formasında olan bir labirintdə tələyə düşdü. O, öz yolunu yuxarı sol plitədən başlayır və aşağı sağ plitəyə çatmaq istəyir. Hər hansı bir plitədə olarkən, o, dörd əsas istiqamətdən istənilən birində qonşu plitəyə keçə bilər.
Ancaq gözləyin! Hər bir plitənin öz rəngi var və hər rəngin özünəməxsus xüsusiyyəti var! Bu barədə düşünmək belə Bessinin başını ağrıtmağa başlayır:
Əgər plitə qırmızıdırsa, o zaman ondan keçmək mümkün deyil.
Əgər plitə çəhrayıdırsa, onun üzərində sərbəst şəkildə hərəkət etmək olar.
Əgər plitə narıncıdırsa, onun üzərində sərbəst şəkildə hərəkət etmək olar, lakin bundan sonra Bessidən portağal iyi gəlməyə başlayır.
Əgər plitə mavidirsə, onun içərisində piranyalar var və onlar Bessiyə yalnız o zaman keçməyə icazə verəcəklər ki, ondan portağal iyi gəlsin.
Əgər plitə bənövşəyidirsə, onda Bessi seçilmiş istiqamətdə növbəti plitəyə sürüşəcək (yalnız o halda ki, ondan keçə bilməsin). Əgər həmin plitə də bənövşəyidirsə, Bessi bənövşəyi olmayan bir plitədə dayanana və ya keçilməz bir plitəyə rast gələnə qədər sürüşməyə davam edəcək. Sürüşmə zamanı bir plitədən keçmək bir hərəkət hesab olunur. Bənövşəyi plitələr həmçinin Bessidəki portağal iyini aradan qaldırır.
Bessiyə yuxarı sol plitədən aşağı sağ plitəyə minimum sayda hərəkətlə çatmağa kömək edin.
Birinci sətirdə labirintin sətir və sütun sayını bildirən iki tam ədəd və m~(1 \le n, m \le 1000) verilmişdir.
Sonrakı sətirdə labirinti təsvir edən hər birində tam ədəd verilmişdir:
ədədi qırmızı plitəni bildirir.
ədədi çəhrayı plitəni bildirir.
ədədi narıncı plitəni bildirir.
ədədi mavi plitəni bildirir.
ədədi bənövşəyi plitəni bildirir.
Yuxarı sol və aşağı sağ plitələrdə həmişə ədədi olacaq.
Bessinin labirintdən keçmək üçün etməli olduğu minimum hərəkət sayını bildirən bir tam ədəd, əgər bu mümkün deyilsə isə çap edin.
Əgər siz bənövşəyi plitələrin necə işlədiyini tam olaraq başa düşmürsünüzsə, aşağıda verilmiş nümunə onların davranışını izah edir.
Bu nümunədə Bessi bir xana aşağı və iki xana sağa keçir, sonra isə daha bir xana sağa sürüşür. Sonra o, bir xana yuxarı, bir xana sola və bir xana aşağı keçir, bu zaman daha iki xana aşağı sürüşür. Sonda o, daha bir xana sağa keçir. Bunların hamısı cəmi hərəkət təşkil edir (DRRRULDDDR).
Nümunə 1