C. Хэдэн квадрат байна вэ?

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

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

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

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

Танд 0-1 гэсэн квадрат матриц өгөгдөв. Түүн дотор хэдэн квадрат байна вэ? Квадрат өргөн нь 1-тэй тэнцүү хатуу хүрээтэй дөрвөлжин байна. Квадрат дор хаяж $2 × 2$ хэмжээтэй байна. Бид зөвхөн хоёр төрлийн квадратад анхаарал хандуулж байна.

  1. Бүх тал нь матрицын талтай парралель байх квадрат

  2. Бүх тал нь матрицын талтай диагональ байх квадрат

Жишээ нь доор өгөгдсөн матрицуудаас 1-р төрөлд багтах цорын ганц квадрат байна.

0000000 

0111100 

0100100 

0100100 

0111100

Төрлөөсөө үл хамааран квадрат нь дор хаяж нэг $1$ агуулах ёстой ба өнцгөөрөө болон аль нэг талаараа өөр нэг $1$ -т хүрэх боломжгүй байна. Мэдээж хэрэг квадтаруудын талуудын урт ижил байх ёстой.

Тэгвэл энэхүү матрицад хэдэн дөрвөлжин байн вэ?

Оролт

Эхний мөр $t$ ($1 ≤ t ≤ 10000$) гэсэн бүхэл тоо агуулж байгаа ба $t$ нь оролтод хийгдсэн сорилын тохиолдлуудын тоо юм. Бүх тохиолдол нь $n$ and $m$ ($2 ≤ n, m ≤ 250$) гэсэн бүхэл тоо агуулсан мөрөөр эхлэх ба энэ үед $n$ нь эгнээний тоо бол $m$ нь баганы тоо юм. Доорх $n$ мөрнүүд нь тус бүрдээ (0$ or 1$) бүхий $m$ тэмдэгтүүдийг агуулж байна. Бүх сорилын тохиолдлуудад орсон тэмдэгтүүдийн нийлбэр тоо нь аливаа оролтод $10^{6}$ -аас хэтрэхгүй байна.

Гаралт

$i$ дахь мөрөн дахь $i$ дахь сорилын тохиолдын хариутай $t$ гэсэн мөрүүдийг гарга.

Орчуулсан: Энхгэрэл

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

Оролт
2
8 8
00010001
00101000
01000100
10000010
01000100
00101000
11010011
11000011
10 10
1111111000
1000001000
1011001000
1011001010
1000001101
1001001010
1010101000
1001001000
1000001000
1111111000
Гаралт
1
2
Оролт
1
12 11
11111111111
10000000001
10111111101
10100000101
10101100101
10101100101
10100000101
10100000101
10111111101
10000000001
11111111111
00000000000
Гаралт
3
Сэтгэгдлүүдийг ачааллаж байна...