Robot-tozsoran
Professor otaq təmizliyini avtomatlaşdırmaq üçün bir robot-tozsoran hazırlamağa qərar verdi. Bu robot-tozsoran sensorları vasitəsilə məkanı skan edərək çirklilik səviyyəsini müəyyənləşdirir və çirklilik matrisini tərtib edir.
Verilən çirklilik matrisinə əsasən, otağı təmizləməyə haradan başlamağın daha səmərəli olduğunu müəyyənləşdirin ki, mümkün qədər çox çirk toplansın. Robot-tozsoranın hərəkət edə biləcəyi addımların sayı və hərəkət alqoritmi R (sağa), L (sola), U (yuxarı), D (aşağı) hərflərindən ibarət bir mətn sətiri ilə verilir. Robot-tozsoran otağın sərhədinə çatdıqda və divara doğru hərəkət etməyə çalışdıqda, əks istiqamətdə hərəkət edir.
Robot-tozsoranın maksimum nə qədər çirk toplaya biləcəyini və onu hansı hüceyrəyə yerləşdirmək lazım olduğunu müəyyən edin.
Giriş məlumatları
Birinci sətirdə otağın hündürlüyü və eni olan N və M ədədləri (2 ≤ N, M ≤ 100) verilir.
İkinci sətirdə robot-tozsoranın atacağı addımların sayı olan K ədədi (1 ≤ K ≤ 10 000) verilir.
Üçüncü sətir robot-tozsoranın hərəkət alqoritmini təyin edən ardıcıllığı ehtiva edir. Növbəti N sətirdə uyğun hüceyrədəki çirklilik səviyyəsi P[ij]
(0 ≤ P[ij]
≤ 100) olan M ədəd verilir.
Çıxış məlumatları
Bir sətirdə üç ədəd boşluqla ayıraraq verin: robot-tozsoranın yığa biləcəyi maksimum çirk miqdarı, robot-tozsoranı yerləşdirmək lazım olan hüceyrənin sətir və sütun nömrəsi.
Əgər belə hüceyrələr bir neçə varsa, indekslərin ən kiçik cəmi olanı seçin, əgər belə də bir neçə varsa, otağın sol tərəfinə daha yaxın olanı seçin.
İzah
Robot-tozsoranı (4,1) hüceyrəsinə yerləşdirdikdə, dərhal 8 vahid çirk yığır, sonra ardıcıl olaraq dörd addım sağa (RRRR) ataraq ümumilikdə 34 vahid çirk yığır. Robot indi divarın yanındadır və sağa addım atmaq mümkün olmadığından (R), əks istiqamətdə (L) addım atılır, lakin bu hüceyrə artıq çirkdən təmizlənib. Sonra sonuncu sağa addım (R) atılaraq artıq təmizlənmiş hüceyrəyə gedilir.
Nümunəyə aid təsvir
Robot aşağıdakı hüceyrə ardıcıllığını keçəcək:
(4,1) R -> (4,2) R -> (4,3) R -> (4,4) R -> (4,5) R L -> (4,4) R -> (4,5).