Еж в саду - Найти маршрут

@Mikstereo · Регистрация: 05.11.2018

Студворк — интернет-сервис помощи студентам

Лес разбит на квадраты и в каждом квадрате находятся яблоки. Еж находится в верхнем левом квадрате леса и хочет попасть в нижний правый квадрат таким образом, чтобы собрать наибольшее количество яблок. Еж может перемещаться только в соседние (справа и снизу) квадраты и собирает яблоки во всех квадратах, в которых он побывал.
Определить маршрут, по которому перемещался еж собирая яблоки. При прочих равных условиях еж предпочитал движение вниз.
Входные данные:В первой строке дано два числа N и M (1 <= M, N <= 1000) - количество строк и столбцов в разбиении леса на квадраты;
В последующих N строках по M целых чисел (0..1000) в каждой строке - количество яблок в каждом квадрате леса.
Выходные данные:В выходной поток вывести в виде таблицы по строкам и стобцам (через один пробел) нули и единицы. Единицой обозначается квадрат, пройденный ежом.
Пример входного файла(input.txt):
3 3
1 1 1
2 4 2
3 3 3
Пример выходного файла(output.txt):
1 0 0
1 1 0
0 1 1
Задачу почти решил, 1 тест не проходит, вот мое решение, контрпример никак не выходит подобрать:

Pascal

var a,b:array[0..1000,0..1000] of longint;
n,i,j,m,k,m1,x,y,k1:longint;
begin
  readln(n,m);
  for i:=1 to n do
    begin
      for j:=1 to m do
        read(a[i,j]);
      readln;
    end;
   for i:=2 to m do
    a[1,i]:=a[1,i]+a[1,i-1];
   for i:=2 to n do
    a[i,1]:=a[i,1]+a[i-1,1];
   for i:=2 to n do
      for j:=2 to m do
        if a[i-1,j]>a[i,j-1]
          then a[i,j]:=a[i,j]+a[i-1,j]
          else a[i,j]:=a[i,j]+a[i,j-1];
    i:=n;
    j:=m;
    while(I>0)and(J>0) do begin
      if a[i-1,j]>a[i,j-1]
        then begin 
              b[i-1,j]:=1;
              i:=i-1;
             end
        else begin 
              b[i,j-1]:=1;
              j:=j-1;
             end;
     end;
   b[n,m]:=1;
   for i:=1 to n do
    begin
      for j:=1 to m do
        write(b[i,j],' ');
      writeln;
    end;
end.

@Mikstereo · 28.02.2019, 18:36 **[ТС]**

Не по теме:

Ап темы

@кот Бегемот · 28.02.2019, 19:54

Знакомая задача. Лет 10 назад я её решал... Классика ДП

@Mikstereo · 28.02.2019, 22:40 **[ТС]**

Сообщение от кот Бегемот

Знакомая задача. Лет 10 назад я её решал... Классика ДП

Что в моем решении не так? Где там ошибка?

Добавлено через 1 час 43 минуты
Задачу решил.Ошибки таковы:
1)b[1,1] всегда равно единице;
2)не верно обработан случай, когда первые 2 строки содержат только нули.

@Mikstereo
	28.02.2019, 18:36 [ТС] #2
	Не по теме: Ап темы 0

@кот Бегемот Платежеспособный зверь 8835 / 4269 / 1621 Регистрация: 28.10.2009 Сообщений: 11,407
	28.02.2019, 19:54	3
	Знакомая задача. Лет 10 назад я её решал... Классика ДП 0

@Mikstereo 98 / 36 / 18 Регистрация: 05.11.2018 Сообщений: 231
	28.02.2019, 22:40 [ТС]	4
	Сообщение от кот Бегемот Знакомая задача. Лет 10 назад я её решал... Классика ДП Что в моем решении не так? Где там ошибка? Добавлено через 1 час 43 минуты Задачу решил.Ошибки таковы: 1)b[1,1] всегда равно единице; 2)не верно обработан случай, когда первые 2 строки содержат только нули. 0

Опции темы