SLIKAR - Slikar

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

// {$APPTYPE CONSOLE}
 {$mode delphi}

uses math, sysutils;

const
    dx : array[1..4] of integer = (0,0,1,1);
    dy : array[1..4] of integer = (0,1,0,1);

type
    Data = class
        b, w, r : integer;
    end;

var
    n, i, j : integer;
    a, b : array[1..555,1..555] of char;

procedure fill(sx, sy, len : integer; c : char);
var
    i, j : integer;
begin
    for i:= sx to sx + len - 1 do
        for j:= sy to sy + len - 1 do
            b[i,j] := c;
end;

function color(sx, sy, len : integer) : Data;
var
    res : Data;
    kq : array[1..4] of Data;
    cur, best, btr, bde, tr, de, i, j, z : integer;
begin
    res := Data.Create;
    
    for i:=sx to sx + len - 1 do
        for j:=sy to sy + len - 1 do
            if a[i,j]='0' then inc(res.b)
            else inc(res.w);
            
    if len = 1 then
    begin
        b[sx,sy] := a[sx,sy];
        // if b[sx,sy] <> a[sx,sy] then inc(res.r);
        color := res;
        exit;
    end;

    z := len div 2;

    for i:=1 to 4 do
        kq[i] := color( sx + dx[i] * z, sy + dy[i] * z, z);

    best := 1000000000;

    for tr := 1 to 4 do
        for de := 1 to 4 do if de <> tr then
        begin
            cur := kq[tr].w + kq[de].b;
            for i := 1 to 4 do if (i<>de) and (i<>tr) then cur := cur + kq[i].r;
            if cur < best then
            begin
                best := cur;
                btr := tr;
                bde := de;
            end;
        end;

    fill( sx + dx[btr] * z, sy + dy[btr] * z, z, '0');
    fill( sx + dx[bde] * z, sy + dy[bde] * z, z, '1');

    res.r := best;
    color := res;
end;


begin
    readln(n);
    for i:=1 to n do
    begin
        for j:=1 to n do read(a[i,j]);
        readln;
    end;

        writeln(color(1, 1, n).r);
        for i:=1 to n do
        begin
            for j:=1 to n do
                write(b[i,j]);
            writeln;
        end;
end.

Download