АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

0 ба 1 цифрүүдээс тогтох матриц өгөгджээ.

1-ээр тэмдэглэгдсэн нүднүүдийг дүүргэгдсэн (будагдсан) нүднүүд гэж нэрлэе.

Хоёр нүд баруун, зүүн, дээд, доод болон диагоналиудаараа залгаатай бол тэдгээрийг хөрш буюу холбогдсон нүднүүд гэж хэлнэ.

Тухайлбал :

XXX

XYX 

XXX

Энэ жишээн дээр Y-ээр тэмдэглэгдсэн нүд X-ээр тэмдэглэгдсэн бүх нүднүүдтэй холбоотой байна гэдгийг харуулж байна.

1 буюу түүнээс олон дүүргэгдсэн нүднүүд хоорондоо холбоотой бол тэдгээрийг нэг муж гэж үзнэ. 

Нэг мужийн дүүргэгдсэн нүднүүд нөгөө мужийн дүүргэгдсэн нүднүүдтэй шууд холбоотой биш байна.

Тэгвэл өгөгдсөн N x M хэмжээтэй матриц дахь хамгийн том дүүргэгдсэн мужийн нүдний тоог хэвлэнэ үү?

Нэг матриц дотор хэд хэдэн муж байж болно.

Жишээлбэл :

Дараах 3 х 3 хэмжээтэй матриц дээр 2 ширхэг муж байна.

Хамгийн том нь зүүн дээд хэсэгт байрлах муж бөгөөд 3 нүднээс тогтож байна.

Жижиг нь баруун доод буланд 1 ширхэг нүднээс тогтож байна.

110

100

001

Оролтын хэлбэр 

Эхний мөрөнд матрицын мөрийн тоо N тоо өгөгдөнө.

Хоёрдугаар мөрөнд матрицын баганын тоо болох M тоо өгөгдөнө.

Дараагийн N ширхэг мөр бүрд M ширхэг matrits[i][j] матрицын элементүүд өгөгдөнө.

Хязгаарлалт:

0 <  N,M < 10

Гаралтын хэлбэр

Матриц дахь хамгийн том холбогдсон мужийн нүдний тоог хэвлэнэ.

Жишээ

Оролт

4

4

1 1 0 0

0 1 1 0

0 0 1 0

1 0 0 0

Гаралт

5

Тайлбар

X-ээр тэмдэглэгдсэн хоёр ширхэг муж байгаа нь дараах хүснэгтээс харагдаж байна.

X X 0 0     1 1 0 0

0 X X 0     0 1 1 0

0 0 X 0     0 0 1 0

1 0 0 0     X 0 0 0

Эхний муж нь 5 ширхэг нүднээс, дараагийн муж нь 1 ширхэг нүднээс тогтож байна.

Бид хамгийн том мужийн хэмжээг хэвлэх учир эхний мужийн хэмжээг хэвлэж байна.

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх