ROBOT

Hãng Carrel đã thiết kế một loại robot mới phục khảo sát mọi loại địa hình. Tuy vậy, robot cần nhiều nhiên liệu hơn khi di chuyển trên các địa hình gồ ghề và ít nhiên liệu khi đi trên các địa hình bằng phẳng. Điều hạn chế duy nhất là robot chỉ có thể đi từng bước theo một trong 4 hướng Đông , Tây, Nam, Bắc đối với vị trí hiện tại của mình. Robot có khả năng liên lạc với vệ tinh để nhận được bản đồ địa hình và tự tính toán đường đi tối ưu tới đích sao cho ít tốn nhiên liệu nhất. Tuy vậy, cán bộ nghiên cứu phụ trách theo dõi hoạt động của robot cần có chương trình độc lập xác định đường đi này để nạp nhiên liệu cho robot. Bình nhiên liệu của robot cho phép nó đi được 9 999 bước nếu mỗi bước cần một đơn vị nhiên liệu.
Từ vệ tinh, robot nhận được bản đồ địa hình dưới dạng lưới ô vuông kích thước m*n ô (0 < m, n ≤ 100), trên mỗi ô ghi một số nguyên dương xác định chi phí nhiên liệu đi qua ô đó, m là số dòng và n là số cột của lưới. Các dòng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Robot cũng đã được biết trước toạ độ điểm xuất phát và điểm đích cần tới.

Yêu cầu: Cho biết bản đồ địa hình và toạ độ các điểm đầu , cuối đường đi. Hãy tính nhiên liệu cần nạp

Dữ liệu: Vào từ file văn bản ROBOT.INP, gồm nhiều bộ dữ liệu:

+ Dòng đầu tiên chứa số nguyên t - số bộ tests trong file,

+ Mỗi test bao gồm một nhóm dòng, trong đó:

- Dòng đầu tiên chứa 2 số nguyên m n,

- m dòng tiếp theo: mỗi dòng chứa n số nguyên, mô tả một dòng của bản đồ,

- dòng cuối cùng chứa 4 số nguyên xác định toạ độ ô xuất phát và ô đích.

Kết quả: Đưa ra file văn bản ROBOT.OUT: với mỗi test đưa ra một số nguyên trên một dòng xác định lượng nhiên liệu cần nạp.

Ví dụ:

ROBOT.INP	ROBOT.OUT
3 5 5 1 1 5 3 2 4 1 4 2 6 3 1 1 3 3  5 2 3 1 2 2 1 1 1 1 1 1 5 5  5 4 2 2 15 1 5 1 15 1 5 3 10 1 5 2 1 1  8 13 2 15 1 1 1 4  10 10 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 1 1 1 1  1 1 10 10	10 15 19

TEST - CODE