SLIKAR - Slikar
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=512;
snode=400000;
var
f1,f2:text;
vt0,vt1,vtx,vty,vt,n:longint;
// timeold:longint;
kq,a:array[1..MAXN,1..MAXN] of longint;
color,diff1,diff0,diff,s0,s1:array[1..snode] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1); close(f2);
end;
procedure inp;
var
i,j:longint;
ch:char;
begin
readln(f1,n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(f1,ch);
if ch='0' then a[i,j]:=0 else a[i,j]:=1;
end;
readln(f1);
end;
end;
procedure build(i,u1,u2,v1,v2:longint);
var
mu,mv:longint;
begin
if (u1=u2) then
begin
if a[u1,v1]=0 then
begin
s0[i]:=1; s1[i]:=0;
diff0[i]:=0; diff1[i]:=1;
diff[i]:=0;
end
else //a[u1,v1]=1
begin
s0[i]:=0; s1[i]:=1;
diff0[i]:=1; diff1[i]:=0;
diff[i]:=0;
end;
exit;
end;
mu:=(u1+u2)>>1; mv:=(v1+v2)>>1;
build(i<<2-2,u1, mu,v1,mv); build(i<<2-1,u1, mu,mv+1,v2);
build(i<<2 ,mu+1,u2,v1,mv); build(i<<2+1,mu+1,u2,mv+1,v2);
s0[i]:=s0[i<<2-2]+s0[i<<2-1]+s0[i<<2]+s0[i<<2+1];
s1[i]:=s1[i<<2-2]+s1[i<<2-1]+s1[i<<2]+s1[i<<2+1];
diff0[i]:=s1[i]; diff1[i]:=s0[i];
diff[i]:=maxlongint;
for vt0:=i<<2-2 to i<<2+1 do
for vt1:=i<<2-2 to i<<2+1 do
if vt0<>vt1 then
begin
vtx:=0; vty:=0;
for vt:=i<<2-2 to i<<2+1 do
if (vt<>vt0) and (vt<>vt1) then
if vtx=0 then vtx:=vt else vty:=vt;
diff[i]:=min(diff[i],diff0[vt0]+diff1[vt1]+diff[vtx]+diff[vty]);
end;
end;
var
i,j:longint;
procedure cal(i,u1,u2,v1,v2,k:longint);
var
mu,mv:longint;
begin
if k=0 then exit;
if k=1 then
begin
for i:=u1 to u2 do
for j:=v1 to v2 do
kq[i,j]:=k;
exit;
end;
if u1=u2 then
begin
kq[u1,v1]:=a[u1,v1];
exit;
end;
mu:=(u1+u2)>>1; mv:=(v1+v2)>>1;
for vt0:=i<<2-2 to i<<2+1 do
for vt1:=i<<2-2 to i<<2+1 do
if vt0<>vt1 then
begin
vtx:=0; vty:=0;
for vt:=i<<2-2 to i<<2+1 do
if (vt<>vt0) and (vt<>vt1) then
if vtx=0 then vtx:=vt else vty:=vt;
if diff[i]=diff0[vt0]+diff1[vt1]+diff[vtx]+diff[vty] then
begin
color[vt0]:=0; color[vt1]:=1; color[vtx]:=2; color[vty]:=2;
cal(i<<2-2,u1, mu,v1, mv,color[i<<2-2]);
cal(i<<2-1,u1, mu,mv+1,v2,color[i<<2-1]);
cal(i<<2 ,mu+1,u2,v1, mv,color[i<<2 ]);
cal(i<<2+1,mu+1,u2,mv+1,v2,color[i<<2+1]);
exit;
end;
end;
end;
procedure ans;
begin
writeln(f2,diff[1]);
for i:=1 to n do
begin
for j:=1 to n do write(f2,kq[i,j]);
writeln(f2);
end;
end;
begin
// timeold:=getTickCount;
openF;
inp;
build(1,1,n,1,n);
cal(1,1,n,1,n,2);
ans;
closeF;
// writeln(getTickCount-timeold);
end.