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. | 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. 1 6 7 s 5 s 7 1 4 3 4 2 4 7 B 7 6 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 A 1 2 6 7 5 7 6 5 6 7 1 2 3 4 2 4 7 B 7 H 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 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 0j Max B m 1 j Max END FOR i 1 TO m DO B i 1 A i 1
