ĐƯỜNG H M DÀI NH T ( 7 ĐI M)Ầ Ấ ỂCÁC NHÀ KH O SÁT Đ A CH T ĐÃ ...

Bài 3 . Đường h m dài nh t ( 7 đi m)ầ ấ ể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.10 21 3 7D  li u vàoữ ệ  : Ghi trong file text, tên file là BL3.INP g m hai dòng:ồ11 31 12 14­ Dòng đ u ghi hai s  nguyên M và N ( 0<M  ầ ố   100; 0 < N 5 21 13 16100).­ M dòng ti p theo, m i dòng ghi N s  nguyên  aế ỗ ố

_i

 (0< a

i

   100, i = 1,..,N).

H1

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.OUT3   4  510  21    3    711  31  12  14 5   21  13  16

H ƯỚ NG D N CH M Ẫ Ấ

MÔN : TIN H C 12Ọ====Yêu c u: Th i gian test m i b  không quá 5 giây. Quá th i gian quy đ nh không ầ ờ ỗ ộ ờ ịcho đi m.ể