Çəpər#6579
Cənab Dokmai nadir çiçəklər yetişdirən biridir. O, nadir və yüksək dəyərli çiçəkləri M sıra və N sütundan ibarət düzbucaqlı torpaq sahəsində əkir. O, çoxlu oğurluq problemləri ilə üzləşdiyi üçün çiçəklərini oğrulardan qorumaq məqsədilə hasarlar tikib. Çiçəklərin dəyərləri fərqli olduğundan, bəzi sahələr daha yaxşı qorunur.
Təəssüf ki, onun hasarları zamanla köhnəlir və bəziləri dağılıb. Mövcud vəziyyəti qiymətləndirmək üçün cənab Dokmai bir xəritə çəkir və hər torpaq sahəsinə bir nömrə təyin edir. Onun xəritəsində bir rəqəm hasar olan sahəni, sıfır isə hasar olmayan və əkin üçün uyğun olan sahəni göstərir. Şəkil 1 11 sıra və 12 sütundan ibarət xəritə nümunəsini göstərir.
Şəkil 1. Çiçək əkmək üçün torpaq sahəsinin təsviri.
Oğru torpaq sahəsinə hər hansı xarici sahədən (şəkildə vurğulanan) daxil ola bilər. Lakin, əgər sahədə hasar varsa, bu, oğrunun daxil olmaq üçün hasarı kəsməli olduğu anlamına gəlir. Oğru torpaq sahəsinə daxil olduqdan sonra müəyyən bir sahəyə keçmək üçün daha çox hasar kəsməli ola bilər. Bir neçə hasarın kəsilməsi çox vaxt və səy tələb edə bilər.
Fərz edək ki, oğru bir sahədən ona bitişik olan digər sahəyə üfüqi və ya şaquli istiqamətdə hərəkət edə bilər, lakin diaqonal istiqamətdə deyil. Məsələn, əgər o, 5-ci Sıra 7-ci Sütundakı sahədədirsə, 4-cü Sıra 7-ci Sütuna, ya da 6-cı Sıra 7-ci Sütuna, ya da 5-ci Sıra 6-cı Sütuna, ya da 5-ci Sıra 8-ci Sütuna keçə bilər. Lakin, məsələn, 4-cü Sıra 6-cı Sütuna keçə bilməz.
Daha sonra fərz edək ki, bir sahənin təhlükəsizlik səviyyəsi oğrunun həmin sahəyə daxil olmaq üçün kəsməli olduğu minimum hasar sayıdır. Məsələn, 6-cı Sıra 6-cı Sütundakı sahənin təhlükəsizlik səviyyəsi 2, 4-cü Sıra 5-ci Sütundakı sahənin təhlükəsizlik səviyyəsi 1, 1-ci Sıra 3-cü Sütundakı sahənin təhlükəsizlik səviyyəsi 0-dır. Qeyd etmək vacibdir ki, sıra və sütun indeksləri 1-dən başlayır.
Cənab Dokmai indi çox bahalı çiçəklər əkmək istəyir, buna görə də ən təhlükəsiz sahələri axtarır. O, həmçinin ən yüksək təhlükəsizlik səviyyəsinə malik sahələrin sayını bilmək istəyir. Qeyd edək ki, xəritədə yalnız 0 ilə təmsil olunan sahələr çiçək əkmək üçün uyğundur. Cənab Dokmai çiçək əkmək üçün yeni sahə yaratmaq məqsədilə heç bir hasarı çıxarmaq niyyətində deyil.
Sizin vəzifəniz ən yüksək təhlükəsizlik səviyyəsini və ən yüksək təhlükəsizlik səviyyəsinə malik sahələrin sayını müəyyən edən bir proqram yazmaqdır.
Girişin ilk sətri test hallarının sayı olan T ≤ 10 rəqəmini ehtiva edir. Qeyd edək ki, eyni sətirdəki tam ədədlər bir boşluq ilə ayrılır.
Test halının ilk sətri iki tam ədəd R və C (5 ≤ R, C ≤ 1000) ehtiva edir. Birinci tam ədəd xəritə sahələrinin sıra sayını R, ikincisi isə sütun sayını C göstərir.
Sətirlər 2-dən R+1-ə qədər hər bir sıranın sahə məlumatlarını ehtiva edir, müvafiq olaraq 1-ci Sıradan R-ci Sıraya qədər. Hər sətirdə C tam ədəd var, burada 0 çiçək əkmək üçün uyğun olan sahəni, 1 isə hasarı təmsil edir.
Qeyd: xəritədə həmişə çiçək əkmək üçün uyğun olan ən azı bir sahə var. Həmçinin, əgər Java proqramlaşdırma dilindən istifadə edirsinizsə, giriş məlumatlarını oxumaq üçün BufferedReader və StreamTokenizer istifadə etməyiniz tövsiyə olunur.
Hər test halı üçün 2 tam ədəd göstərin. Birincisi, çiçək əkmək üçün uyğun olan torpaq sahəsinin ən yüksək təhlükəsizlik səviyyəsini göstərən qeyri-mənfi tam ədəddir. İkincisi, ən yüksək təhlükəsizlik səviyyəsinə malik sahələrin sayıdır. İki rəqəm bir boşluq ilə ayrılır.
İzah: Hər iki nümunə üçün, aşağıdakı ulduzlar ən yüksək təhlükəsizlik səviyyəsinə malik sahəni təmsil edir. Qalın altı xətlə göstərilən rəqəmlər oğrunun ən az hasar kəsərək ən yüksək təhlükəsizlik sahəsinə gedə biləcəyi bəzi yolları təmsil edir.
Nümunə 1