Cho một lưới vuông kích thước . Giả sử góc trên bên trái là điểm xuất phát ◎, tọa độ là , trục hướng sang phải là dương, trục hướng xuống dưới là dương, mỗi cạnh ô vuông có độ dài là 1.
Một chiếc xe ô tô xuất phát từ điểm khởi đầu ◎ đi về phía điểm đích ▲ ở góc dưới bên phải, tọa độ là .
Tại một số giao điểm của lưới, có đặt các trạm xăng để xe có thể đổ xăng trên đường đi. Xe phải tuân thủ các quy tắc sau trong quá trình di chuyển:
Xe chỉ có thể đi dọc theo các cạnh của lưới. Sau khi đổ đầy xăng, xe có thể đi được cạnh lưới. Khi xuất phát, xe đã được đổ đầy xăng. Không có trạm xăng tại điểm xuất phát và điểm đích.
Khi xe đi qua một cạnh lưới, nếu tọa độ hoặc tọa độ giảm (đi sang trái hoặc đi lên), xe phải trả chi phí là , ngược lại (đi sang phải hoặc đi xuống) thì miễn phí.
Nếu xe gặp trạm xăng trên đường đi, bắt buộc phải đổ đầy xăng và trả chi phí đổ xăng là .
Khi cần thiết, có thể xây dựng thêm trạm xăng tại các điểm lưới (giao điểm) và phải trả chi phí xây dựng là (chưa bao gồm chi phí đổ xăng sau khi xây xong).
đều là các số nguyên dương và thỏa mãn ràng buộc: .
Hãy thiết kế thuật toán để tìm một lộ trình từ điểm xuất phát đến điểm đích với tổng chi phí thấp nhất.
Dữ liệu:
Dòng đầu tiên chứa các giá trị .
Bắt đầu từ dòng thứ hai là một ma trận 0-1 kích thước , mỗi dòng gồm giá trị.
Giá trị tại dòng thứ cột thứ của ma trận là 1 biểu thị rằng tại giao điểm có sẵn một trạm xăng, là 0 biểu thị chưa có trạm xăng. Các số trên cùng một dòng được phân cách bởi dấu cách.
Kết quả:
Khi chương trình kết thúc, xuất ra chi phí nhỏ nhất.
