HỌC TIN CÙNG THỦ KHOA

Đề bài: Cho bảng A gồm MxN ô. Từ ô (i,j) có thể di chuyển sang 3 ô (i+1,j), (i+1,j–1) và (i+1,j+1). Hãy xác định một lộ trình đi từ hàng 1 đến hàng M sao cho tổng các ô đi qua là lớn nhất.

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

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

var g : text;
    N, M : integer;
    a: array [1..MAXM, 1..MAXN] of integer;
    F: array[1..MAXM, 0.. MAXN+1] 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;

procedure Init;
begin
        fillchar(F, sizeof(F), 0);
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;

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

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

procedure TruyVet(i, j : integer);
begin
        if i = 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-1, j] + a[i, j] then
                                TruyVet(i-1, j)
                        else TruyVet(i-1, j+1);
                write(g, ' -> (', i, ', ', j, ')');
        end;
end;


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

BEGIN
        Nhap;
        Init;
        QHD;
        InKQ;

END.