Şimalın kralı
Qış gəldi (yoxsa artıq gəlir? bu günlərdə kim bilir) və yeni kral Şimalda yüksəlir. Bu günlərdə məlumat sürətlə yayılır... Məhz buna görə də, siz, gənc kral, çox vaxtınız qalmayıb. Sizə bayraqdarlar ordusunu toplamaq lazımdır. Lakin bir suala cavab vermək, görünür, düşündüyünüzdən daha çətindir. Siz iddia edə biləcəyiniz krallıq nə qədər böyükdür və onun müdafiəsi üçün neçə nəfər göndərilməlidir? Məsləhətçiləriniz potensial dövləti diqqətlə araşdırıb və xəritənin istənilən hissəsini düşmənlərinizə qarşı tam müdafiə etmək üçün neçə bayraqdarın lazım olduğunu müəyyən ediblər. Siz, sevən və qayğıkeş kral olaraq, ordunuzda xidmət etməli olan insanların sayını minimuma endirmək istəyirsiniz. Hərbi məsləhətinizin krallığı necə daha yaxşı müdafiə etmək barədə düzgün qərar qəbul etməsi üçün sizə lazım olan ordunun ölçüsünü müəyyən etməlisiniz.
Xoşbəxtlikdən, düşmən orduları o qədər də qabaqcıl deyil. Sizə yalnız üfüqi və ya şaquli hərəkət edən ordulardan qorunmaq kifayətdir (ordu bayraqdarlarınızın yanından diaqonal keçə bilməz). Krallığınız, xəritənin hüdudlarından kənarda bir yerdən başlayaraq və müdafiə olunan əraziləri keçmədən qalaya çatmaq mümkün olmadıqda müdafiə olunmuş sayılır. Xəritədə 0 ilə işarələnmiş kvadratlar yüksək dağlar və ya divarlardır, heç kim onları keçə bilməz. Siz onları bayraqdarlarla müdafiə etməməlisiniz. Divarın (və ya bizim vəziyyətimizdə xəritənin sərhədlərinin) arxasında nə olduğunu bilmədiyiniz üçün ən pis ssenariyə hazırlaşmalısınız. Planlarınızda xəritənin hüdudlarından kənarda olan hüceyrələri tutmamalısınız.
Şəkil - Nümunəyə aid təsvir - krallıq minimal 37 bayraqdar ordusu ilə müdafiə olunur, mövqeləri xaç işarəsi ilə göstərilmişdir. Krallıq şəbəkə şəklində təsvir edilmişdir. Siz krallıq haqqında yeni bir şey öyrənməməlisiniz və ya bayraqdarların yerini tapmamalısınız. Bu məsələləri sizin hərbi məsləhətiniz həll etməlidir.
Giriş məlumatları
Məsləhətçilərinizin gətirdiyi düzbucaqlı strateji xəritə şəklində verilir. Xəritənin hər kvadratı ehtimal olunan orduya qarşı müdafiə üçün lazım olan bayraqdarların sayını göstərir. Xəritənin formatı belədir: ilk sətir R və C tam ədədlərini (3 ≤ R, C ≤ 300) - xəritənin ölçülərini ehtiva edir. Sonra R sətir gəlir, hər biri C tam ədəd c[i] (0 ≤ c[i] ≤ 100000) - hər kvadratın müdafiəsi üçün lazım olan bayraqdarların sayını göstərir. Sonda r (0 < r < R - 1) və c (0 < c < C - 1) - xəritədə qalanızın mövqeyi verilir.
Çıxış məlumatları
Krallığın müdafiəsi üçün ordunuzun mümkün olan ən kiçik ölçüsünü çıxış edin.