D. Цикл

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Петя "$0$" болон "$1$"-ээс бүрдсэн тэгш өнцөгт хүснэгтэд маш дуртай. Саяхан тэрээр ийм нэг хүснэгт ээжээсээ бэлэг болгон авчээ. Уг хүснэгт нь $n$ мөр, $m$ баганатай байв. Мөрүүд нь дээрээс доош $1$-ээс $n$ хүртэл, баганууд нь зүүнээс баруун тийш $1$-ээс $m$ хүртэл дугаарлагдсан байлаа. Петя шуудхан л боломжит хамгийн урт догь циклийг олохоор шийдэв.

Цикл бол ижил талтай $2$ нүднүүд (зэргэлдээ нүднүүд) бүхий хосоороо ялгаатай нүднүүдийн дараалал бөгөөд эхний нүд нь хамгийн сүүлийн нүдтэй ижил талтай байна. Дараах нөхцөлүүдийг нэгэн зэрэг хангаж байх циклийг догь гэж үзнэ. Үүнд:

  • Цикл нь бүхэлдээ дан "$1$"-ийг агуулах нүднүүдээс бүрдэнэ.
  • Циклийн нүд бүр нь уг циклд харьяалагдах $2$ ширхэг нүдтэй ижил талтай байна.
  • "$1$"-ийг агуулсан хүснэгтийн нүд бүр нь циклд харьяалагдана, эсвэл циклийн гадна оршино (доорх тодорхойлолтыг харна уу).

"Гадна" гэх ойлголтыг албан ёсоор тодорхойлохын тулд хавтгай дээр цикл зуръя. Циклийн $(i, j)$ ($i$ нь мөрийн дугаар, $j$ нь баганы дугаар) нүднүүд нь хавтгай дээрх $(i, j)$ гэсэн координатад харгалзана гэж үзье. Шулуун хэрчим нь циклд харьяалагдах, ижил талтай нүднүүдэд харгалзах цэгийн хосуудыг холбоно гэж үзье. Тиймээс бид өөртэйгээ огтлолцохгүй, шүргэлцдэггүй, хаалттай олон шугамыг авах болно. Олон шугам нь хавтгайг хоорондоо холбогдсон 2 хэсэгт хуваана: хязгааргүй бүсийн хэсэг болон хязгаарлагдмал бүсийн хэсэг. Үүнийг $(r, c)$ нүд нь циклд харьяалагдахгүй бол циклийн гадна байх ба хавтгайд харгалзах $(r, c)$ координатууд нь хязгааргүй бүсийн хэсэгт байршина гэж ойлгож болох юм.

Хүснэгтэнд байх хамгийн урт догь циклийн уртыг олоход Петяд туслаарай. Циклийн урт нь тухайн циклд харьяалагдах нүднүүдийн тоогоор тодорхойлогдоно.

Оролт

Эхний мөр нь хүснэгтийн мөр ба баганыг харуулах $n$ ба $m$ ($1≤n, m≤1000$) 2 бүхэл тоог агуулна. Дараагийн $n$ мөрүүд нь $m$ тооны тэмдэгтүүдийг агуулна. Тэмдэгтүүд нь "$0$" эсвэл "$1$" байна.

Гаралт

Хүснэгтийн хамгийн урт догь циклийн уртыг харуулах тоог хэвлээрэй. Хэрэв ийм цикл оршихгүй бол "0" гэж хэвлээрэй.

Орчуулсан: Солонго

Жишээ тэстүүд

Оролт
3 3
111
101
111
Гаралт
8
Оролт
5 5
01010
10101
01010
10101
01010
Гаралт
0
Оролт
7 7
1111111
1000101
1000101
1000101
1000111
1000001
1111111
Гаралт
24
Оролт
5 5
11111
10001
10101
10001
11111
Гаралт
0

Тэмдэглэл

Эхний жишээнд, нэг л цикл байх ба энэ нь догь байна.

Хоёр дахь жишээнд, цикл байхгүй байна.

Гурав дахь жишээнд, $2$ догь цикл байна. Эдгээрийн урт нь $12$ болон $24$ байна.

Дөрөв дэх жишээнд, нэг л цикл байх ба энэ нь догь биш байна. Учир нь уг цикл дотор "$1$"-ийг агуулах нүд байна.

Сэтгэгдлүүдийг ачааллаж байна...