## Editorial for Hình vuông 0 1

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

var t,k:byte;
m,n,i,j,max:integer;
a:array[0..1,0..1,1..5000] of integer;

procedure wr;
begin
writeln(max);
end;

function min(x,y,z:integer):integer;
begin
if (x<=y) and (x<=z) then min:=x
else
begin
if y<=z then min:=y else min:=z;
end;
end;

begin
fillchar(a,sizeof(a),0);
max:=0;
for i:=1 to m do
begin
t:=i mod 2;
for j:=1 to n do
begin
if k=1 then
begin
a[t,0,j]:=0;
a[t,1,j]:=min(a[1-t,1,j-1],a[1-t,1,j],a[t,1,j-1])+1;
if a[t,1,j]>max then
begin
max:=a[t,1,j];

end;
end
else
begin
a[t,1,j]:=0;
a[t,0,j]:=min(a[1-t,0,j-1],a[1-t,0,j],a[t,0,j-1])+1;
if a[t,0,j]>max then
begin
max:=a[t,0,j];
end;
end;
end;
end;
wr;
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 1000
int dp[N+1][N+1], a[N+1][N+1], m, n;

inline int get(int a, int b, int c, int d) {
return dp[c][d] - dp[a][d] - dp[c][b] + dp[a][b];
}

int main() {
scanf("%d%d",&m,&n);
int res = 0;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j) {
scanf("%d", &a[i][j]); dp[i][j] = 1;
if(a[i][j] == a[i-1][j] && a[i-1][j] == a[i-1][j-1] && a[i-1][j-1] == a[i][j-1])
res = max(res, dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]))+1);
}
#ifdef __WATASHI
putchar(10); for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= n; ++j) printf("%d ", dp[i][j]);
putchar(10);
}
#endif
printf("%d\n", res);
return 0;
}


program qbrect;
uses    math;

type    bin = 0..1;
var     f:array[-1..1001] of longint;
a:array[0..1001,0..1001] of bin;
i,maxS,m,n,j,target:longint;
inp:text;

procedure input;
var     i,j:longint;
begin
assign(inp,'');
reset(inp);
for i:=1 to m do
begin
for j:=1 to n do read(inp,a[i,j]);
end;

end;

procedure process(row:longint);
var     i,j:longint;
l,r:array[-2..1002] of longint;
begin
fillchar(l,sizeof(l),0);
fillchar(r,sizeof(r),0);
for i:=1 to n do
if a[row,i] = target then inc(f[i])
else f[i]:=0;
l[1]:=0;
for i:=2 to n do
begin
j:=i-1;
while (j>0) and (f[j]>=f[i]) do
j:=l[j];
l[i]:=j;
end;
r[n]:=n+1;
for i:=n-1 downto 1 do
begin
j:=i+1;
while (j<n+1) and (f[j]>=f[i]) do
j:=r[j];
r[i]:=j;
end;

for i:=1 to n do
begin
if f[i]>0 then
maxS:=max(maxS,min(r[i]-l[i]-1,f[i]));
end;
end;

begin
fillchar(a,sizeof(a),0);
input;
maxS:=0;
for i:=1 to m do
process(i);
target:=1;
for i:=1 to m do
process(i);
write(maxS);
end.


#### Code mẫu của RR

uses math;
var
i,j,top,res,m,n:longint;
a:array[0..1011,1..1011] of longint;
down,left,right,stack:array[0..1011] of longint;

procedure solve(k:longint);
var
i,j:longint;
begin
down[0]:=0;
down[n+1]:=down[0];
for i:=1 to m do
begin
for j:=1 to n do
if a[i,j]=k then down[j]:=down[j]+1
else down[j]:=0;

top:=0; stack[0]:=0;
for j:=1 to n do
begin
while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
left[j]:=stack[top]+1;
inc(top); stack[top]:=j;
end;

top:=0; stack[0]:=n+1;
for j:=n downto 1 do
begin
while (top>0) and (down[stack[top]]>=down[j]) do dec(top);
right[j]:=stack[top]-1;
inc(top); stack[top]:=j;
end;

for j:=1 to n do
res:=max(res,min(down[j],right[j]-left[j]+1));
end;
end;

begin
for i:=1 to m do
for j:=1 to n do

solve(0);
solve(1);
writeln(res);
end.


#### Code mẫu của hieult

#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
//#include<conio.h>

using namespace std;

#define FOR(i, a, b) for(int i=(a), _b=(b); i < _b; ++i)
#define FORU(i, a, b) for(int i=(a), _b=(b); i <= _b; ++i)
#define FORD(i, a, b) for(int i=(a), _b=(b); i >= _b; --i)
#define maxn 1111

int l[2][maxn], r[2][maxn], h[2][maxn], a[maxn][maxn];

int main(){
//freopen("QBRECT.in","r",stdin);
int m,n,kq = 0;
scanf("%d %d",&m,&n);
FORU(i, 1, m) FORU(j, 1, n) scanf("%d",&a[i][j]);
memset(h,0,sizeof(h));
FORU(i, 1, m) FOR(t, 0, 2){
FORU(j, 1, n) {
if(a[i][j]==t)
h[t][j]++;
else h[t][j] = 0;
}
h[t][0] = -1; h[t][n+1] = -1;
FORU(j, 1, n){
l[t][j] = j;
while(h[t][l[t][j]-1]>=h[t][j]) l[t][j] = l[t][l[t][j]-1];
}
FORD(j, n, 1){
r[t][j] = j;
while(h[t][r[t][j]+1]>=h[t][j]) r[t][j] = r[t][r[t][j]+1];
}
FORU(j, 1, n){
kq = max(kq,min(h[t][j],r[t][j]-l[t][j]+1));
}
}
printf("%d",kq);
//getch();
}


#### Code mẫu của ll931110

{\$MODE DELPHI}
Program QBSQUARE;
Const
input  = '';
output = '';
maxn = 1000;
Type
rec = record
n0,n1: integer;
end;
Var
n,m,max: integer;
a: array[1..maxn,1..maxn] of integer;
F: array[0..maxn,0..maxn] of rec;
ch: boolean;

Procedure init;
Var
fi: text;
i,j: integer;
Begin
Assign(fi, input);
Reset(fi);

For i:= 1 to m do
For j:= 1 to n do read(fi, a[i,j]);

Close(fi);
End;

Procedure gens;
Var
t0,t1,i,j: integer;
Begin
Fillchar(F[0], sizeof(F[0]), 0);
For i:= 1 to m do
Begin
t0:= 0;
t1:= 0;

For j:= 1 to n do
Begin
If a[i,j] = 0 then inc(t0) else inc(t1);
F[i,j].n0:= F[i - 1,j].n0 + t0;
F[i,j].n1:= F[i - 1,j].n1 + t1;
End;
End;
End;

Function calc(x,y,z,t: integer): rec;
Var
u: rec;
Begin
u.n0:= F[z,t].n0 - F[z,y - 1].n0 - F[x - 1,t].n0 + F[x - 1,y - 1].n0;
u.n1:= F[z,t].n1 - F[z,y - 1].n1 - F[x - 1,t].n1 + F[x - 1,y - 1].n1;
calc:= u;
End;

Procedure solve;
Var
i,j: integer;
t: rec;
Begin
ch:= false;
max:= 1;

For i:= 1 to m do
For j:= 1 to n do
If (i + max <= m) and (j + max <= n) then
Begin
t:= calc(i,j,i + max,j + max);
If t.n0 * t.n1 = 0 then
Begin
ch:= true;
While (i + max < m) and (j + max < n) and (t.n0 * t.n1 = 0) do
Begin
t:= calc(i,j,i + max + 1,j + max + 1);
If t.n0 * t.n1 = 0 then inc(max);
End;
End;
End;
End;

Procedure printresult;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
If not ch then writeln(fo, 1) else writeln(fo, max + 1);
Close(fo);
End;

Begin
init;
gens;
solve;
printresult;
End.


#### Code mẫu của skyvn97

#include<stdio.h>
#define MAX   1111
int a[MAX][MAX];
int f[MAX][MAX];
int m,n;
int min(int x,int y,int z)
{
int m;
m=x;
if (y<m) m=y;
if (z<m) m=z;
return (m);
}
void init(void)
{
int i,j;
scanf("%d",&m);
scanf("%d",&n);
for (i=1;i<=m;i=i+1)
for (j=1;j<=n;j=j+1)
scanf("%d",&a[i][j]);
}
void optimize(void)
{
int i,j,s,r;
for (i=1;i<=m;i=i+1) f[i][1]=1;
for (i=1;i<=n;i=i+1) f[1][i]=1;
for (i=2;i<=m;i=i+1)
for (j=2;j<=n;j=j+1)
{
s=a[i][j]+a[i][j-1]+a[i-1][j]+a[i-1][j-1];
if (s*(s-4)==0) f[i][j]=min(f[i][j-1],f[i-1][j],f[i-1][j-1])+1;
else f[i][j]=1;
}
r=0;
for (i=1;i<=m;i=i+1)
for (j=1;j<=n;j=j+1)
if (r<f[i][j]) r=f[i][j];
printf("%d\n",r);
}
int main(void)
{
init();
optimize();
}


#### Code mẫu của khuc_tuan

#include <stdio.h>

int m, n;
int h0[1000], h1[1000], l1[1000], l0[1000];

int main() {
int i, j, xx, t, result = 0;
scanf("%d%d", &m, &n);
for(i=0;i<m;++i) {
t = 0;
for(j=0;j<n;++j) {
scanf("%d", &xx);
h1[j] = (xx==1) ? h1[j]+1 : 0;
h0[j] = (xx==0) ? h0[j]+1 : 0;
l1[j] = (h1[j]>result) ? (j==0 ? -1 : l1[j-1]) : j;
l0[j] = (h0[j]>result) ? (j==0 ? -1 : l0[j-1]) : j;
if(j-l1[j]>result) t = 1;
if(j-l0[j]>result) t = 1;
}
result += t;
}
printf("%d\n", result);
return 0;
}