Cho một hình chữ nhật kích thước MxN (với 0<M,N<100). Trên mỗi ô của hình chữ nhật có chứa một số dương. Một rô bốt được đặt vào một ô của hình chữ nhật. Rô bốt có thể đi từ ô này sang ô kia nếu hai ô có chung cạnh và không được ra khỏi phạm vi hình chữ nhật. Hãy tìm một cách di chuyển rô bốt từ ô (x1,y1) qua các ô của hình chữ nhật đến ô (x2,y2) sao cho số ô mà rô bốt đi quá không quá K ô và toognr các số của các ô mà rô bốt đi qua là nhỏ nhất ( kể cả ô xuất và ô kết thúc). Với k là một số nguyên dương cho trước.
Yêu cầu:
-Dữ liệu vào là file văn bản Robot.inp có cấu trúc sau :
Dòng đầu là 7 số nguyên M,N,K,x1,y1,x2,y2 giữa các số cách nhau một khoảng trống.
M dòng tiếp theo, mỗi dòng gồm N số nguyên dương là các số tương ứng trong hình chữ nhật MxN.
-Dữ liệu ra là file văn bản Robot.out có cấu trúc như sau :
Dòng đầu tiên là hai số nguyên S,H với S là tổng các số trong các ô mà rô bốt đã đi từ ô (x1,y1) đến ô (x2,y2) và H là số ô mà rô bốt đã đi qua tính cả ô (x1,y1) và (x2,y2).
H dòng tiếp theo, mỗi dòng gồm hai số x,y lần lượt là các ô mà rô bốt đi qua.
Nếu không tìm được đường đi thì quy ước S=0 và H=0.
Robot.inp
7 5 10 2 1 6 5
1 3 1 7 8
5 15 2 8 6
4 12 1 9 10
5 10 3 1 9
3 2 12 2 11
15 4 3 2 8
10 7 4 10 7
Robot.out
36 9
2 1
3 1
4 1
5 1
5 2
6 2
6 3
6 4
6 5