Các nhà khảo sát địa chất đã ghi lại độ sâu tối đa ứng với các vị trí có thể đào được mà không gặp mạch nước ngầm của một khu đất có dạng hình chữ nhật. Các số đo được ghi lại trên một bản đồ gọi là bản đồ độ sâu. Bản đồ độ sâu là một hình chữ nhật được chia thành MxN ô vuông, mỗi ô vuông ghi một số nguyên biểu thị độ sâu có thể đào được tại vị trí đó của khu đất. Người ta muốn đào một đường hầm thoát nước dài nhất của khu đất này bắt đầu từ một ô có độ sâu nào đó (không nhất thiết bắt đầu ở các ô biên) và kết thúc ở một ô tùy ý. Do nước chảy từ nơi cao xuống nơi thấp, nên đường hầm thoát nước khi đào qua các ô phải theo nguyên tắc đi từ ô có độ sâu nhỏ hơn đến ô chung cạnh có độ sâu lớn hơn.
Yêu cầu : Hãy đưa ra độ dài tối đa của đường hầm thoát nước có thể đào được.
Dữ liệu vào : Ghi trong file text, tên file là BL3.INP gồm hai dòng:
- Dòng đầu ghi hai số nguyên M và N ( 0<M $\leq$100; 0 < N $\leq$100).
- M dòng tiếp theo, mỗi dòng ghi N số nguyên ai
(0< ai $\leq$100, i = 1,..,N).
Dữ liệu ra : Ghi ra file text tên file là BL3.OUT gồm một số nguyên là số ô mà đường hầm dài nhất đi qua.
BL3.INP BL3.OUT
3 4 5
10 21 3 7
11 31 12 14
5 21 13 16
Edited by phamngochung9a, 17-02-2016 - 19:42.
