Codeforces Round #803 (Div. 2)
2 өдрийн дараа |
Codeforces Round #804 (Div. 2)
8 өдрийн дараа |
C. Хэдэн квадрат байна вэ?
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 64 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд 0-1 гэсэн квадрат матриц өгөгдөв. Түүн дотор хэдэн квадрат байна вэ? Квадрат өргөн нь 1-тэй тэнцүү хатуу хүрээтэй дөрвөлжин байна. Квадрат дор хаяж $2 × 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