Козак Вус və matris#10354
Kazak Vus x ölçüsündə bir matris əldə etdi (yəni, sətir və sütundan ibarət bir matris). Bu matrisin elementləri yalnız sıfırlar və birlərdən ibarətdir.
Kazak, matrisin elementləri arasındakı Manhattan məsafəsi haqqında məlumat aldı. Məlum oldu ki, əgər bir matris elementi nömrəli sətirdə və nömrəli sütunda yerləşirsə, digər element isə nömrəli sətirdə və nömrəli sütunda yerləşirsə, bu elementlər arasındakı Manhattan məsafəsi \mid i - p \mid + \mid j - k \mid (yəni, elementlərin koordinat fərqlərinin modullarının cəmi) kimi hesablanır.
Bundan sonra Vus başa düşdü ki, matrisin hər hansı bir elementinin "gözəlliyi" bu elementdən ən yaxın bir elementinə olan məsafədir. Qeyd edək ki, hər hansı bir birin "gözəlliyi" -a bərabərdir. Üstəlik, Kazak öyrəndi ki, belə matrislərdə mütləq ən azı bir bir var.
Sizin vəzifəniz sadədir — matrisin ən "gözəl" elementinin "gözəlliyini" tapın.
Birinci sətir və (1 \leq n,m \leq 20) tam ədədlərini ehtiva edir — matrisin sətir və sütunlarının sayı.
Sonrakı sətirin hər biri rəqəmi a_{i,1}, a_{i,2},...,a_{i,m} (0 \leq a_{i,j} \leq 1) ehtiva edir — matrisin elementlərinin dəyərləri.
Ən azı bir birin olacağı təmin edilir.
Tək bir ədəd çıxarın — maksimum "gözəllik".
Nümunə 1
Nümunə 2
Birinci misaldakı matris üçün hər bir elementin "gözəlliyini" matrisə yazsaq:
1 0 1
2 1 2
Gördüyümüz kimi, matrisin iki elementi — (ikinci sətir, birinci sütun) və (ikinci sətir, üçüncü sütun) ən böyük "gözəlliyə" malikdir — 2.
İkinci misal üçün "gözəllik" matrisi:
1 0 1 0
2 1 1 0
3 2 2 1
n = 1 məhdudiyyətləri üçün düzgün işləyən həllər ən azı bal toplayacaq.
n = 2 məhdudiyyətləri üçün düzgün işləyən həllər ən azı bal toplayacaq.