mong các bạn giúp mình bài sau:(cà rốt)

[hai6f2009]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Bài 2. Thỏ và cà rốt
Trên đường đi tìm thức ăn trở về nhà, Thỏ tình cờ phát hiện một khu vườn trồng toàn cà rốt. Khu vườn hình chữ nhật có kích thước MxN được chia thành các ô vuông 1 đơn vị, mỗi ô chứa một lượng cà rốt nhất định. Vốn là món ăn ưa thích của Thỏ nên Thỏ muốn nhặt càng nhiều cà rốt càng tốt nhằm để dành cho màu đông sắp đến. Nhưng Thỏ rất nhát gan và sợ chủ nhân của khu vườn phát hiện, nên nó phải nghĩ cách để vượt qua khu vườn càng nhanh càng tốt mà lại kiếm được nhiều cà rốt nhất có thể. Thỏ xuất phát từ vị trí ở góc trên trái khu vườn (ô (1,1)) muốn đi qua khu vườn để đến dòng thứ M (vì nó biết cuối khu vườn (dòng M) là rừng rậm – nơi có hang trú ẩn của nó). Thỏ nghĩ rằng đi theo quy tắc như sau thì không bị chủ vườn phát hiện:
- Chỉ có thể đi theo một dòng chia nhỏ trên vườn ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của bảng chữ nhật.
- Những dòng hoặc cột nào đã đi qua thì không được đi ngược lại dòng hoặc cột đó.

Nhưng nó không biết đi như thế nào theo quy tắc trên để nhặt được nhiều cà rốt nhất. Hãy chỉ ra đường đi giúp Thỏ có được nhiều cà rốt nhất.
Dữ liệu vào: file CAROT.INP gồm:
- Dòng 1 chứa 2 số M và N ( )
- M dòng tiếp theo, mỗi dòng chứa N số nguyên dương là lượng cà rốt có trên mỗi ô vuông đơn vị.
Dữ liệu ra: file CAROT.OUT gồm:
- Dòng đầu chứa lượng thức ăn nhiều nhất mà con kiến có thể ăn được.
- Dòng 2 lần lượt chứa từng cặp (x,y) là vị trí dòng và cột của ô mà Thỏ đi qua. Mỗi cặp (x,y) cách nhau 1 dấu cách.
Các số trên một dòng cách nhau 1 dấu cách.
Ví dụ:
CAROT.INP CAROT.OUT
3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1 45
(1,1) (2,1) (2,2) (2,3) (3,3)

Giải thích: Thỏ đi theo các ô như sau:

 

[quanghero100]

CONST fi='CAROT.INP';
      fo='CAROT.OUT';
      Nmax=100;
      Mmax=100;
TYPE toado=RECORD x,y:INTEGER; END;
VAR a:ARRAY[1..Nmax,1..Mmax] OF INTEGER;
    L:ARRAY[0..Nmax,0..Mmax] OF LONGINT;
    m,n:INTEGER;
    f:TEXT;
PROCEDURE input;
VAR i,j:INTEGER;
BEGIN
   assign(f,fi);
   reset(f);
   readln(f,m,n);
   FOR i:=1 TO m DO
     BEGIN
        FOR j:=1 TO n DO read(f,a[i,j]);
        readln(f);
     END;
   close(f);
END;

FUNCTION max(a,b:INTEGER):INTEGER;
BEGIN
   max:=a;
   IF max<b THEN max:=b;
END;


PROCEDURE QHD;
VAR i,j:INTEGER;
BEGIN
    FOR i:=1 TO m-1 DO
      FOR j:=1 TO n DO L[i,j]:=max(L[i-1,j],L[i,j-1])+a[i,j];
    FOR j:=1 TO n DO L[m,j]:=L[m-1,j]+a[m,j];
END;

PROCEDURE output;
VAR i,j,li,lj,dem:INTEGER;
    max:LONGINT;
    kq:ARRAY[1..Nmax+Mmax] OF toado;
BEGIN
   assign(f,fo);
   rewrite(f);
   max:=0;
   FOR j:=1 TO n DO
     IF max<L[m,j] THEN BEGIN max:=L[m,j]; lj:=j; END;
   writeln(f,max);
   li:=m; dem:=0;
   REPEAT
       inc(dem);
       kq[dem].x:=li; kq[dem].y:=lj;
       IF L[li,lj]=L[li-1,lj]+a[li,lj] THEN dec(li)
       ELSE dec(lj);
   UNTIL (li=0) OR (lj=0);
   FOR i:=dem DOWNTO 1 DO write(f,'(',kq[i].x,',',kq[i].y,') ');
   close(f);

END;

BEGIN
   input;
   QHD;
   output;
END.