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.
Nội dung trích xuất từ tài liệu:
Bài toán di chuyển từ Tây sang Đông Bài toán di chuyển từ Tây sang ĐôngCho 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áttạ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ãytì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ố ghitrê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ớinhữ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ácB[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 DOEND;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 #include using namespace std;#define MAX 100#define MAXINT 2000000000ifstream 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; iA[i][j]; fi.ignore(); }}int Min(int i, int j){ int m=i-1; if (B[i][j-1] for (i=1; ivoid Trace(int i, int j){ if (i==0) fo