ĐỘ CHÊNH LỆCH NHỎ NHẤT (4 ĐIỂM)CHO BẢN MÔ PHỎNG MỘT VÙNG ĐẤT TRÊN SAO...

Bài 4: Độ chênh lệch nhỏ nhất (4 điểm)Cho bản mô phỏng một vùng đất trên sao Hỏa là một bảng A gồm m hàng, n cột (chỉ số hàng được đánh thứtự từ trên xuống dưới, chỉ số cột được đánh từ trái sáng phải, mỗi loại chỉ số được bắt đầu từ 1), mỗi ô ghimột số nguyên chỉ độ cao của ô đất tương ứng (độ cao có thể âm). Một rô-bốt thám hiểm sao Hỏa cần dichuyển từ vùng đất này đến vùng đất khác được thể hiện trên bản đồ từ ô (x1,y1) đến vị trí ô (x2,y2) bằngcách đi qua các ô liên tiếp chung cạnh trong bản đồ. Để rô-bốt di chuyên được an toàn cần tìm một hànhtrình của rô-bốt sao cho độ chênh lệch cao nhất giữa hai ô liên tiếp trên đường đi là bé nhất (độ chênh lệchgiữa hai ô là giá trị tuyệt đối của hiệu độ cao hai ô đó)Yêu cầu: Biết m, n cùng các giá trị A[i,j] chỉ độ cao tại các ô (i,j) (1≤i≤m; 1≤j≤n) của bảng và vị trí (x1,y1);(x2,y2). Hãy tìm độ chênh lệch lớn nhất là bé nhất trên một đường đi nào đó của rô-bốt từ ô (x1,y1) đến ô(x2,y2).Dữ liệu vào từ tệp BAI4.INP:- Dòng đầu tiên là hai số m, n (1≤m, n ≤100)- Dòng thứ hai ghi bốn số x1, y1, x2, y2 (1≤x1, x2≤m; 1≤y1, y2≤n)- m dòng tiếp theo, dòng thứ i ghi các số A[i,j] chỉ độ cao của các ô trong bảng (A[i,j] có giá trị tuyệt đốikhông quá 10

⁹

)Kết quả ra ghi vào tệp BAI4.OUT: Số nguyên không âm biểu diễn độ cao chênh lệch lớn nhất là bé nhấtđã tìm được.Ví dụ:BAI4.INP BAI4.OUT Giải thích 3 44 Đường đi của rô-bốt: 1 1 3 3(1,1)  (2,1)  (2,2)  (2,3)  (3,3)-2 9 3 4 0 3 7 -4 8 -9 9 10