Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBSQUARE - Hình vuông 0 1

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbsquare


Cho một bảng kích thước MxN, được chia thành lưới ô vuông đơn vị M dòng N cột ( 1 <= M, N <= 1000 )

Trên các ô của bảng ghi số 0 hoặc 1. Các dòng của bảng được đánh số 1, 2... M theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số 1, 2..., N theo thứ tự từ trái qua phải

Yêu cầu:

Hãy tìm một hình vuông gồm các ô của bảng thoả mãn các điều kiện sau:

1 - Hình vuông là đồng nhất: tức là các ô thuộc hình vuông đó phải ghi các số giống nhau (0 hoặc 1)

2 - Cạnh hình vuông song song với cạnh bảng.

3 - Kích thước hình vuông là lớn nhất có thể

Input

Dòng 1: Ghi hai số m, n

M dòng tiếp theo, dòng thứ i ghi N số mà số thứ j là số ghi trên ô (i, j) của bảng

Output

Gồm 1 dòng duy nhất ghi kích thước cạnh của hình vuông tìm được

Example

Input:
11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1

Output:
7

Được gửi lên bởi:special_one
Ngày:2008-06-13
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Được add lên bởi Võ Khánh Trung

hide comments
2022-03-09 03:32:28
Prefix sum+chặt nhị phân AC.
Code: https://ideone.com/MlYZZJ

Last edit: 2022-03-09 03:34:31
2021-05-27 18:03:26
Tham khảo: https://vnspoj.github.io/problems/QBSQUARE
2021-02-21 02:47:55
Linh Linh
2020-05-14 17:05:23
o(n^2) auto ac
2017-11-13 04:14:24
Bê nguyên code AC QBRECT sang thay đổi 1 tí nộp toàn làm sai lúc sau đọc lại thấy cả hình vuông 0 =.=
=))) nhây quá
frostpixel aka.How 2 AC
2017-08-19 11:06:20 Con Bò Huyền Thoại
https://kienthuc24h.com/qbsquare-spoj-hinh-vuong-0-1/
2017-07-07 11:21:26
Bac noi dung. Trau ez AC =))
2017-07-07 10:16:07
Trau AC ez =)))
2017-02-09 15:17:29
cin cout phai them dong ios_base::sync_with_stdio(false); la AC
2016-11-02 09:44:28
left - right cai cho khoe :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.