ptmeilin
14-12-2008, 00:02
Em ko bít truy vết dù bt đã làm xong nhưng tới truy vết là bí hà, vd như cho bài toán:
inp:cho mang a
4 5
2 4 6 2 1
3 6 1 7 3
4 6 0 2 1
7 2 9 5 3
đỉnh xuất phát là a[1,3] tìm đường đi ngắn nhất, chỉ được đi xuống (xống ba ô ở dưới á, trên ví dụ nếu đỉnh xuất fat1 là 6 thì ba đỉnh có thể xuống đc là 6 hoắc 1 hoặc 7, y cầu xủa đề ta sẽ fai3 xuống ô 1 là a[2,3] ),
công thức của nó là: b[i,j]:=min(b[i-1,j-1]+abs(a[i,j]-a[i-1,j-1]),b[i-1,j]+abs(a[i,j]-a[i-1,j],b[i-1,j+1]+abs(a[i,j]-a[i-1,j+1]);
output:
9 {tổng các đỉnh}
(4,2)->(3,3)->(2,3)->(1,3) (truy vết)
làm ơn giúp em cái công thức truy vết Y_Y
inp:cho mang a
4 5
2 4 6 2 1
3 6 1 7 3
4 6 0 2 1
7 2 9 5 3
đỉnh xuất phát là a[1,3] tìm đường đi ngắn nhất, chỉ được đi xuống (xống ba ô ở dưới á, trên ví dụ nếu đỉnh xuất fat1 là 6 thì ba đỉnh có thể xuống đc là 6 hoắc 1 hoặc 7, y cầu xủa đề ta sẽ fai3 xuống ô 1 là a[2,3] ),
công thức của nó là: b[i,j]:=min(b[i-1,j-1]+abs(a[i,j]-a[i-1,j-1]),b[i-1,j]+abs(a[i,j]-a[i-1,j],b[i-1,j+1]+abs(a[i,j]-a[i-1,j+1]);
output:
9 {tổng các đỉnh}
(4,2)->(3,3)->(2,3)->(1,3) (truy vết)
làm ơn giúp em cái công thức truy vết Y_Y