C11CUT - Cắt bảng

Tác giả: ladpro98

Ngôn ngữ: Pascal

program c11cut;
uses    math;
const   fi='';
        cx:array[1..9] of longint = (0,0,0,0,1,2,3,4,0);
        cy:array[1..9] of longint = (1,2,3,4,0,0,0,0,0);
var     a:array[1..4,1..4] of longint;
        check:array[1..4,1..4] of boolean;
        m,n,res:longint;

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

function sum(i,j,x,y:longint):longint;
var     p,t:longint;
begin
        t:=0;
        if i=x then
        for p:=j to y do
        t:=10*t+a[i,p]
        else
        for p:=i to x do
        t:=10*t+a[p,j];
        exit(t);
end;

procedure like(i,j,x,y:longint);
var     p,q:longint;
begin
        for p:=i to x do
        for q:=j to y do
        check[p,q]:=true;
end;

procedure unlike(i,j,x,y:longint);
var     p,q:longint;
begin
        for p:=i to x do
        for q:=j to y do
        check[p,q]:=false;
end;

function ok(i,j,x,y:longint):boolean;
var     p,q:longint;
begin
        for p:=i to x do
        for q:=j to y do
        if check[p,q] then exit(false);
        exit(true);
end;

procedure back(i,j,s:longint);
var     k,x,y:longint;
begin
        if i>m then
        begin
                res:=max(res,s);
                exit;
        end;
        if check[i,j] then
        begin
                if j<n then back(i,j+1,s)
                else    back(i+1,1,s);
                exit;
        end;
        for k:=1 to 9 do
        begin
                x:=i+cx[k];
                y:=j+cy[k];
                if (x<=m) and (y<=n) then
                if ok(i,j,x,y) then
                begin
                        like(i,j,x,y);
                        if j<n then back(i,j+1,s+sum(i,j,x,y))
                        else    back(i+1,1,s+sum(i,j,x,y));
                        unlike(i,j,x,y);
                end;
        end;
end;

begin
        input;
        back(1,1,0);
        write(res);
end.

Download