Bài toán di chuyển từ Tây sang Đông

Cho một bảng A kích thước m x n, trên đó ghi các số nguyên. Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được). Quy tắc: Từ ô A[i, j] chỉ được quyền sang một trong 3 ô A[i, j + 1]; A[i - 1, j + 1]; A[i + 1, j + 1]. Hãy tìm vị trí ô xuất phát và hành trình đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất. 

Gợi ý:
Gọi B[i, j] là số điểm lớn nhất có thể có được khi tới ô A[i, j]. Rõ ràng đối với những ô ở cột 1 thì B[i, 1] = A[i, 1]:

Với những ô (i, j) ở các cột khác. Vì chỉ những ô (i, j – 1), (i – 1, j – 1), (i + 1, j – 1) là có thể sang được ô (i, j), và khi sang ô (i, j) thì số điểm được cộng thêm A[i, j] nữa. Chúng ta cần B[i, j] là số điểm lớn nhất có thể nên B[i, j] = max(B[i, j - 1], B[i - 1, j - 1], B[i + 1, j - 1]) + A[i, j]. Ta dùng công thức truy hồi này tính tất cả các B[i, j]. Cuối cùng chọn ra B[i, n] là phần tử lớn nhất trên cột n của bảng B và từ đó truy vết tìm ra đường đi nhiều điểm nhất.

Cài đặt bằng ngôn ngữ Pascal:

PROGRAM tay_dong;
CONST Max = 2000000000;
VAR A,B,T:ARRAY[0..101,1..100] OF LONGINT;
    Tong:LONGINT;
    m,n,dongcuoi:INTEGER;
PROCEDURE Nhap;
VAR i,j:INTEGER;
BEGIN
    readln(m,n);
    FOR i:=1 TO m DO
        BEGIN
            FOR j:=1 TO n DO read(A[i,j]);
            readln;
        END;
    FOR i:=1 TO n DO
END;

FUNCTION Min(i,j:INTEGER):INTEGER;
VAR m:INTEGER;
BEGIN
    m:=i-1;
    IF B[i,j-1] < B[m,j-1] THEN m:=i;
    IF B[i+1,j-1] < B[m,j-1] THEN m:=i+1;
    Min:=m;
END;

PROCEDURE Taobang;
VAR i,j,d:INTEGER;
BEGIN

    FOR j:=1 TO n DO
        BEGIN
            B[0,j]:=Max;
            B[m+1,j]:=Max;
        END;
   FOR i:=1 TO m DO B[i,1]:=A[i,1];

   FOR j:=2 TO n DO
       FOR i:=1 TO m DO
       BEGIN
           d:=min(i,j);
           B[i,j]:=B[d,j-1]+A[i,j];
           T[i,j]:=d;
       END;
   tong:=B[1,n];
   dongcuoi:=1;
   FOR i:=2 TO m DO
       IF tong>B[i,n] THEN
       BEGIN
           tong:=B[i,n];
           dongcuoi:=i;
       END;

END;

PROCEDURE TruyVet(dong,cot:INTEGER);
BEGIN
    IF cot=0 THEN
         writeln(tong)
    ELSE
    BEGIN
        TruyVet(T[dong,cot],cot-1);
        write(dong,' ');
    END;
END;

BEGIN
    assign(Input,'input.inp'); reset(Input);
    assign(Output,'Output.out'); rewrite(Output);

    Nhap;
    Taobang;
    TruyVet(dongcuoi,n);

    close(Input);
    close(Output);
END.

Cài đặt bằng ngôn ngữ C++

#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100
#define MAXINT 2000000000

ifstream fi("Input.inp");
ofstream fo("Output.out");

int A[MAX+2][MAX+1],B[MAX+2][MAX+1],T[MAX+2][MAX+1],m,n,R,sum;

void Enter()
{
    fi>>m>>n;
    int i,j;
    for (i=1; i<=m; i++)
    {
        for (j=1; j<=n; j++)
            fi>>A[i][j];
        fi.ignore();
    }
}

int Min(int i, int j)
{
    int m=i-1;
    if (B[i][j-1]<B[m][j-1]) m=i;
    if (B[i+1][j-1]<B[m][j-1]) m=i+1;
    return m;
}

void Optimize()
{
    int i,j,d;
    for (j=1; j<=n; j++) B[0][j]=B[m+1][j]=MAXINT;
    for (i=1; i<=m; i++) B[i][1]=A[i][1];

    for (j=2; j<=n; j++)
        for (i=1; i<=m; i++)
        {
            d=Min(i,j);
            B[i][j]=B[d][j-1]+A[i][j];
            T[i][j]=d;
        }

    R=1;
    sum=B[1][n];
    for (i=2; i<=m; i++)
        if (B[i][n]<sum)
        {
            sum=B[i][n];
            R=i;
        }
}

void Trace(int i, int j)
{
    if (i==0)
        fo<<sum<<endl;
    else
    {
        Trace(T[i][j],j-1);
        fo<<i<<" ";
    }
}

int main()
{
    Enter();
    Optimize();
    Trace(R,n);
    fi.close();
    fo.close();
    return 0;
}