Robot lấy hàng

[noithatkienan]

Bài 3. Lấy hàng
Sa mạc được coi như một lưới hình chữ nhật gồm M*N ô vuông. Trên mỗi ô vuông có một số lượng các kiện hàng (các kiên hàng là như nhau) Một robot lấy hàng đi từ ô xác định có toạ độ (1, xp) trên dòng đầu và di chuyển sang ô xác định có toạ độ (m, kt) trên cạnh đối diện của sa mạc, nhưng trong quá trình di chuyển thì nó chỉ có thể đi thẳng về phía trước mặt hoặc chỉ có thể tiến bên trái hoặc bên phải một góc 45o so với hướng di chuyển về cuối.
(Có nghĩa là nếu robot từ ô (i, j) chỉ có thể di chuyển đến một trong 3 ô có toạ độ (i+1, j-1), (i+1, j), (i+1, j+1) nếu các ô này thuộc sa mạc)
Yêu cầu: Hãy xây dựng cho robot một lộ trình lấy hàng từ ô xuất phát đến ô kết thúc sao cho số hàng lấy được là nhiều nhất. Giả thiết rằng robot có khả năng mang hàng không hạn chế.
Dữ liệu vào: cho trong file văn bản layhang.inp có cấu trúc như sau:
+ Dòng 1: ghi 2 số nguyên dương M, N (2<=N<=1000)
+ Dòng i (2<=i<=M+1) trong số M dòng tiếp theo mỗi dòng ghi N số nguyên A[i, 1], A[i, 2], A[i, 3], …, A[i, N] tương ứng là số kiện hàng trên các ô của dòng i.
+ Dòng cuối ghi bốn số nguyên dương x, y, z, t là toạ độ của ô xuất phát và ô kết thúc.
Kết quả: Ghi ra file văn bản layhang.out có cấu trúc như sau:
+ Dòng 1: ghi số S là tổng số hàng lấy được
+ Dòng 2 ghi lộ trình của robot từ ô xuất phát đến ô kết thúc.

layhang.inp


layhang.out


4 4
<div style="text-align: center">1 3 8 2
9 4 7 9
2 5 7 10
3 1 6 8
1 2 4 3​

s=26

(1, 2)--> (2, 3)-->(3, 4)-->(4, 3)​

​</div>

(Các số trên một dòng cách nhau một dấu cách)

[kaka1q2]

Quy hoạch động:
f[i,j] là giá trị hàng lớn nhất robot lấy được từ ô xuất phát để đến ô i,j
ban đầu gán f[1,j]=0, riêng cái f[x,y]=a[x,y] (tọa độ xuất phát)
tiếp theo thì f[i,j]=Max(f[i-1,j-1], f[i-1,j], f[i-1,j+1]) + a[i,j]) (Với 2<=i<=M; 1<=j<=N);
f[z,t] là giá trị cần tìm, sau đó xây dựng công thức truy hồi để tìm đường đi là xong [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[totinhte]

Quy hoạch động thì mình cũng không biết, thế có thể dùng quay lui không nhỉ. Bạn có thể viết đầy đủ cho mình chương trình bằng quy hoach động hoặc quay lui

[nguyenhuongit]

Bài này là bài toán dạng mở đầu khi học tới qhd do đó bạn có thể lạ lẫm với nó, bạn nên đọc thêm vài ebook về qhd sẽ cảm thấy bài toán này cũng đơn giản thôi.
Với bài này thuật toán qhd là tốt nhất rồi đấy, thuật toán quay lui chỉ gây thêm phức tạp không cần thiết cho người viết chương trình thôi. Công thức của bạn T-7 chính xác rồi đấy, bạn dựa vào đó là đủ viết được chương trình hoàn chỉnh được rồi.