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.

Download