HỌC TIN CÙNG THỦ KHOA

Đề bài: Có một ống hình trụ, khi trải phẳng ra có thể là một bảng MxN ô. Giá trị A[i,j] là lượng thức ăn có ở ô ở dòng i cột j. Một con kiến xuất phát từ một ô ở mép bên trái của hình trụ và b sang mép bên phải. Từ ô (i,j) kiến có thể bò sang 1 trong 3 ô (i–1,j+1), (i,j+1) hoặc (i+1,j+1). (Chú ý: vì ống hình trụ nên kiến đang ở dòng 1 có thể bò xuống dòng M và ngược lại). Bò qua ô nào thì kiến mang theo toàn bộ lượng thức ăn ở ô đó. Hãy tìm đường đi mà kiến kiếm được nhiều thức ăn nhất.

Mời các bạn download tại: Click here

const fi = 'CONKIEN.INP';
      fo = 'CONKIEN.OUT';
      MAXM = 1000;
      MAXN = 1000;

var g : text;
    N, M : integer;
    a: array [1..MAXM, 1..MAXN] of integer;
    F: array [1..MAXM, 1.. MAXN] of integer;

procedure Nhap;
var i, j : integer;
begin
    assign(g, fi); reset(g);
    readln(g, M, N);
    for i:=1 to M do
    begin
       for j := 1 to N do  read(g, a[i,j]);
       //readln(g);
    end;
end;

function Max3(x, y, z : integer) : integer;
var max : integer;
begin
    max := x;
    if max < y then max := y;
    if max < z then max := z;
    exit(max);
end;

function TT1(i: integer): integer;
begin
        if i = 0 then exit(M)
                else exit(i-1);
end;

function TT2(i: integer): integer;
begin
        if i = M then exit(1)
                else exit(i+1);
end;

procedure QHD;
var i, j: integer;
begin
    for i:=1 to M do F[i, 1] := a[i, 1];

    for j:= 2 to N do
       for i:= 1 to M do
            F[i, j] := Max3(F[TT1(i), j-1], F[i,j-1], F[TT2(i), j-1])
                       + a[i, j];
end;

procedure TruyVet(i, j : integer);
begin
        if j = 1 then
                write(g, '(', i, ', ' , j, ') ')

        else  // i > 1
        begin
                if F[i, j] = F[i-1, j-1] + a[i, j] then
                        TruyVet(i-1, j-1)
                else
                        if F[i, j] = F[i, j-1] + a[i, j] then
                                TruyVet(i, j-1)
                        else TruyVet(i+1, j-1);
                write(g, ' -> (', i, ', ', j, ')');
        end;
end;


procedure InKQ;
var max, i, k: integer;
begin
        assign(g, fo); rewrite(g);
        max:= -1;
        for i:= 1 to M do
                if max < F[i, N] then
                begin
                        max:= F[i, N];
                        k:= i;
                end;
        writeln(g, max);
        TruyVet(k, N);
        close(g);
end;

BEGIN
        Nhap;
        QHD;
        InKQ;

END.