[help]Thuật toán tìm đường đi có tổng lớn nhất trong mảng 2 chiều - pascal

**SerialKiller1702** · 16-06-2011 09:31

Các bạn giúp thuật toán cho bài này nhé!
Cho 1 lưới o vuông kích thước NxN ( 0<N<=100).TÌm đường đi từ ô (1,1) đến ô (N,N) sao cho tổng các chữ số trên đường đi là lớn nhất.Biết rằng 1 lần di chuyển chỉ đi sang phải 1 ô hoặc đi xuống dưới 1 ô.Tìm tổng lớn nhất và ghi lại đường đi đó thành từng dòn,1 dòng là 1 cặp số chỉ toạ độ x,y của các ô từ vị trí xuất phát(1,1) đến ô (n,n).

vd:
input
5 {la so N}
2 7 2 6 5
7 1 8 1 4
4 9 3 6 4
1 1 9 5 2
9 5 2 6 1

output
46 {tong}
1 1 {cac dong sau la toa do cac vi tri tuong ung}
2 1
3 1
3 2
3 3
4 3
4 4
5 4
5 5

**Dustin Đỗ** · 16-06-2011 10:22

bài này là một trong những bài toán Quy hoạch động đơn giản thôi bạn. Xem bài tham khảo nhé.

Code:

const
  spt = 101;
  fi = 'f.i';
  fo = 'f.o';
var
  n: byte;
  a, b: array[0..spt,0..spt] of integer;
  c: array[0..spt,0..spt] of 0..1;

procedure Input;
var
  f: text;
  i, j: byte;
begin
  assign(f, fi);
  reset(f);
  readln(f,n);
  for i := 1 to n do
    begin
      for j := 1 to n do
        read(f,a[i,j]);
      readln(f);
    end;
  close(f);
end;

procedure Process;
var
  i,j: byte;
begin
  for i := 1 to n do
    for j := 1 to n do
      begin
        b[i,j] := 0;
        c[i,j] := 0;
      end;
  b[1,1] := a[1,1];
  for i := 2 to n do
    begin
      b[1,i] := b[1,i-1] + a[1,i];
      b[i,1] := b[i-1,1] + a[i,1];
    end;
  for i := 2 to n do
    for j := 2 to n do
      if b[i-1,j] > b[i,j-1] then b[i,j] := b[i-1,j] + a[i,j]
      else b[i,j] := b[i,j-1] + a[i,j];
  c[n,n] := 1;
  for i := n downto 1 do
    for j := n downto 1 do
      if c[i,j] = 1 then
        if b[i-1,j] > b[i,j-1] then
          c[i-1,j] := 1
        else c[i,j-1] := 1;
end;

procedure Result;
var
  f: text;
  i, j: byte;
begin
  assign(f, fo);
  rewrite(f);
  writeln(f, b[n,n]);
  for i := 1 to n do
    for j := 1 to n do
      if c[i, j] = 1 then
        writeln(f, i, ' ', j);
  close(f);
end;

begin
  Input;
  Process;
  Result;
end.

có chỗ nào chưa đúg, không hiểu hay chưa hay thì bạn cứ góp ý nhák

**raicars** · 19-06-2011 20:28

aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh

**Trac_dung** · 19-06-2011 21:27

mình cũng có một bài, bạn xem thử nhé

var a,b,c: array[1..100,1..100] of integer;
f: text;
n,min,s: integer;
{===================}
procedure doc;
var i,j: integer;
begin
assign(f,'bai1.inp');
reset(f);
readln(f,s);
for i:= 1 to n do
for j:= 1 to n do
read(f,a[i,j]);
close(f);
end;
{==================}
procedure ghi;
var i,j: integer;
begin
assign(f,'bai1.out');
rewrite(f);
writeln(f,min);
for i:= 1 to n do
for j:= 1 to n do
if c[i,j]<>0 then writeln(f,i,' ',j);
close(f);
end;
{====================}
procedure tim(i,j: byte);
begin
if (i=n) and (j=n) then
begin
if (s+a[i,j])< min then
begin
min:= s+a[i,j];
b[i,j]:= 1;
c:=b;
b[i,j]:=0;
end;
end
else
begin
s:= s+a[i,j];
b[i,j]:=1;
if j< n then tim(i,j+1);
if i< n then tim(i+1,j);
s:= s-a[i,j];
b[i,j]:=0;
end;
end;
{=====================}
begin
doc;
min:= 10000;
s:=0;
fillchar(b,sizeof(b),0);
tim(1,1);
ghi;
end.

**raicars** · 19-06-2011 22:28

aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh aaaaaaaaa ac afcadadasda sfsfs sd dg hsdf dfh fh hfdh dfh