Ən yaxşı daraq

Sıfırlardan və birlərdən ibarət ədədi matrisada ən böyük kvadrat və düzbucaqlı sıfır altmatrisaları tapmaq məsələsinin öhdəsindən gəldikdən sonra, daha ümumi bir problem ortaya çıxıb. Sıfır və birlərdən ibarət matris verilir və vəzifəniz bu matrisada sıfır hüceyrələrdən istifadə etməklə qurula biləcək ən optimal "daqdağı" (ingiliscə "comb") tapmaqdır. Optimal daqdaq, matrisa daxilində ən çox hüceyrəni əhatə edən daqdaq kimi müəyyən edilir. Daqdaqın istənilən "bağı" sıfırlardan ibarət boş olmayan düzbucaqlı sahədir, yəni yalnız sıfırlardan ibarət (özündə sıfırlardan təşkil olunmuş altmatrisa olan) və sahəsi sıfırdan böyük olan bir altmatrisadır. $k$-daqdaq isə (0 \leq k \leq m) şaquli istiqamətdə $k$ ədəd bağı birləşdirərək alınan qurumdur. Bu bağlarda soldan başlanğıc $x$-koordinatı eyni olmalı, yanaşı yerləşən bağların enləri fərqli olmalı və bütün bağlar birlikdə birgə, bir-biri ilə əlaqəli (bitşik) fiqur təşkil etməlidir. $0$-daqdaq həmişə mövcuddur və ölçüsü $0$-dır.

Aşağıda $\text{1}$-ci şəkil etibarlı $7$-daqdağı göstərir. Struktura baxmayaraq $8$ sətri əhatə edir, lakin $7$-daqdaq sayılır, çünki aşağıdan ikinci və üçüncü sətirlər eyni bağı paylaşır (yanaşı bağların enləri fərqlidir, lakin bir bağ bir neçə sətri əhatə edə bilər). $\text{2}$-ci şəkildəki struktur düzgün daqdaq deyil, çünki bağların başladığı sol $x$-koordinatı uyğun gəlmir. Oxşar şəkildə, $\text{3}$-cü struktur doğru daqdaq deyil, çünki birləşdirilmiş fiqur deyil. Qeyd edək ki, ən yaxşı düzbucaqlı yalnız ən yaxşı $1$-daqdaqdır (yəni tək bağdan ibarət daqdaq). Açıqdır ki, matrisa üzrə istənilən uzunluq $k$ üçün ən yaxşı daqdağı tapmaq, yaxud belə daqdaq mövcud deyilsə (yəni ən yaxşı daqdaqın ölçüsü $0$-dır) qeyd etmək olar. Məsələn, $\text{4}$-cü şəkildə ən yaxşı $3$-daqdaq ayrılmışdır (matrisadakı sıfır olmayan elementlər $\text{X}$ ilə qeyd olunub).

Şəki̇l 4

Sizdən tələb olunur ki, verilmiş matrisada sıfırlardan istifadə etməklə qurula biləcək bütün $k$-daqdaqlar (bütün $k$, $0$-dan $m$-ə kimi) arasında ən böyük daqdaqın ölçüsünü müəyyən edəsiniz.