Bài tập về đồ thị ( cần gấp )

hung1xpro96 · 1 Tháng tư 2012

Cho một mảng 2 chiều gồm N dòn M cột . Mỗi ô vuông trong bảng chứa một số nguyên . Tìm trong bảng một HCN con có tổng các số trên các ô là lớn nhất ( HCN này được gọi là lớn nhát trong các HCN thuộc bảng ) .
Một HCN gồm 1 ô 1x1 kề nhau hoặc chiếm toàn bộ bảng .

Dữ liệu vào : HCN.INP

- Dòng 1 : Ghi số N , M ( 1<= N,M <=10000).
- Trong N dòng tiếp theo mỗi dòng gồm M số nguyên .

Dữ liệu ra : HCN.OUT
- Dòng 1 : Ghi tổng của HCN lớn nhất .
- Dòng 2 : Ghi tọa độ góc trái trên cùng của HCN max .
- Dòng 3 : Ghi tọa độ góc phải dưới cùng của HCN max .

vd : HCN.INP
4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

HCN.OUT
15
2 1
4 2
--------------------------------
vd 2 : HCN.INP

4 5
1 2 3 0 -1
2 4 5 -8 -9
1 -10 2 45 7
1 2 3 -15 -5

HCN.OUT
54
3 3
3 5

p_trk · 3 Tháng tư 2012

gửi bạn Hưng ! chúc bạn thi olympic 30-4 tốt

đầu tiên mình xin chúc bạn thi olympic 30-4 thật tốt , sớm mang vinh dự cho trường nhak !
mình gửi bạn bài giải :

Mã:

  const fi='HCN.INP'; fo='HCN.OUT';
 var
   m,n:word;
   a:array[1..100,1..100] of integer;
   kx,ky:array[1..1000] of word;
   max,tong:integer;
   dem,x1,y1,x2,y2: word;
 procedure nhap;
  var
     f:text;
     i,j: word;
  begin
      assign(f,fi); reset(f);
      read(f,n,m);
      for i:=1 to n do
       for j:=1 to m do
        read(f,a[i,j]);
      close(f);
  end;

 procedure init;
  var
    i,j: word;
  begin
      max:=-2576;
      dem:=0;
      for i:=1 to n do
       for j:=1 to m do
        begin
            inc(dem);
            kx[dem]:=i;
            ky[dem]:=j;
        end;
  end;

 procedure xd;
  var
     i,j,t,p:word;
  begin
      for i:=1 to dem do
       for j:=1 to dem do
        if ( kx[i]<=kx[j] ) and ( ky[i]<=ky[j] ) then
        begin
           tong:=0;
           for t:=kx[i] to kx[j] do
            for p:=ky[i] to ky[j] do
             tong:=tong+a[t,p];
           if tong>max then
             begin
                 max:=tong;
                 x1:=kx[i];
                 y1:=ky[i];
                 x2:=kx[j];
                 y2:=ky[j];
             end;
        end;
  end;

 procedure xuat;
  var
    f:text;
  begin
      assign(f,fo); rewrite(f);
      writeln(f,max);
      writeln(f,x1,'  ',y1);
      writeln(f,x2,'  ',y2);
      close(f);
  end;

BEGIN
    nhap;
    init;
    xd;
    xuat;
END.

Starlove: Thân !!!

Tìm kiếm

Tìm kiếm

Bài tập về đồ thị ( cần gấp )

hung1xpro96

p_trk