Пират в подземелье, Нужен второй алгоритм Опции

[1nFinite]

Прошу помомите написать алгоритм задачи
Пират в подземелье

В поисках драгоценных камней пират проваливается в подземелье. План подземелья - матрица NxM комнат с драгоценными камнями. Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой комнате разрешается взять с собой лишь один камень и следовать в любую другую соседнюю с ним комнату. Каждую из комнат пират может посещать неоднократно .

Требуется составить алгоритм- программу определения маршрута посещения пиратом К комнат лабиринта таким образом , чтобы он набрал камней на максимально возможную сумму .

Входные и Выходные . В первой строке входного файла содержаться числа N,M и K
В следующих N строках распологается матрица NxM лабиринта. Каждый элемент матрицы представляется стоимостью камня соответствующей комнаты. Маршрут начинается с левой верхней угловой комнаты лабиринта.

Выходной файл должен содержать единственное число, равное общей стоимости взятых с собой камней.

Пример файла исходных данных:

3 4 7
1 1 1 1
1 1 2 1
1 1 2 3

Выходной файл для данного примера:
12.

[klem4]

а можешь уточнить, что обозначает K , три цифры перед матрицей 3 4 7, это
3х4 - размер, а 7 - К ? какие-то наверное еще есть ограничения на ход, ведь можно просто обойти всю матрицу и собрать все ...

не могупонять в чем соль.

Сообщение отредактировано: klem4 - 30.05.2005 15:29

[1nFinite]

N=3 M=4 K=7
NxM - размер матрицы
K - количество комнат
В данном примере который я написал там
число ходов 7 комнат и он(пират) должет набрать на эти 7 ходов 12 камней
Начанается ход с верхнего левого угла
Он должен набрать на максимальную возможную сумму

[klem4]

т.е всего-то комнат - 3х4=12, но ходов ему можно делать только К, в данном случае 7 ? и при этом можно возвращаться в комнаты, в которых уже был.

хех интересно.

[1nFinite]

Прошу помоч решить задачу :
Пират в подземелье

В поисках драгоценных камней пират проваливается в подземелье. План подземелья - матрица NxM комнат с драгоценными камнями. Камни из одной комнаты имеют одинаковую стоимость. Пирату в каждой комнате разрешается взять с собой лишь один камень и следовать в любую другую соседнюю с ним комнату. Каждую из комнат пират может посещать неоднократно .

Требуется составить алгоритм- программу определения маршрута посещения пиратом К комнат лабиринта таким образом , чтобы он набрал камней на максимально возможную сумму .

Входные и Выходные . В первой строке входного файла содержаться числа N,M и K
В следующих N строках распологается матрица NxM лабиринта. Каждый элемент матрицы представляется стоимостью камня соответствующей комнаты. Маршрут начинается с левой верхней угловой комнаты лабиринта.

Выходной файл должен содержать единственное число, равное общей стоимости взятых с собой камней.

Пример файла исходных данных:

3 4 7
1 1 1 1
1 1 2 1
1 1 2 3

Выходной файл для данного примера:
12.

N=3 M=4 K=7
NxM - размер матрицы
K - количество комнат
В данном примере там
число ходов 7 комнат и он(пират) должет набрать на эти 7 ходов 12 камней
Начанается ход с верхнего левого угла
Он должен набрать на максимальную возможную сумму

Решение этой задачи
(но нужно еще считывать из файла
матрицу NxM)

const n=3; m=4; k=7;
const podz:array[1..n,1..m] of integer=
((1,1,1,1),
(1,1,2,1),
(1,1,2,3));
const move_step:array[1..4,1..2] of shortint=((-1,0),(0,1),(1,0),(0,-1));
type stringK=string[k*3];
var podzemelie:array[1..n,1..m] of integer;
    treasure,max_treasure,i1,j1:integer;
    f:text;
    dec_s:string[7];
    move_step_l:string;
function MovePossible(i,j:byte):boolean;
  begin
  MovePossible:=(1<=i) and (i<=n) and (1<=j) and (j<=m);
  end;
procedure GoNextRoom(i,j,n_step:byte;treasure:integer;log:stringK);
var s,next_i,next_j:byte;
    direction:string[2];
  begin
  inc(treasure,podzemelie[i,j]);
  writeln('Step: ',n_step:3,'; Room(',i,',',j,'); treasure: ',treasure,
    ' Max_treasure: ',max_treasure);
  writeln(f,'<tr><td>',n_step,'</td><td>(',i,',',j,')</td><td>',
    treasure, '</td><td>',max_treasure,'</td><td>',log,'</td></tr>');
  if (n_step<k) then
    for s:=1 to 4 do
      begin
      next_i:=i+move_step[s,1];
      next_j:=j+move_step[s,2];
      if MovePossible(next_i,next_j) then
         begin
         if (log='') then direction:=move_step_l[s]
                     else direction:='-'+move_step_l[s];
         GoNextRoom(next_i,next_j,n_step+1,treasure,log+direction);
         end
      end
  else {n_step>=k}
    if treasure>max_treasure then
      begin
      max_treasure:=treasure;
      writeln(' Max treasure raised to ',max_treasure);
      writeln(f,'<tr><td colspan=5>Max treasure raised to ',
        max_treasure,'; log=',log,'</td></tr>');
      end
  end;

begin
for i1:=1 to n do
for j1:=1 to m do
  podzemelie[i1,j1]:=podz[i1,j1];
max_treasure:=0;
move_step_l:='NESW';
assign(f,'log.txt');
rewrite(f);
GoNextRoom(1,1,1,0,'');
writeln(' Max Treasure:', max_treasure);
writeln(f,' Max Treasure:', max_treasure);
close(f);
end.

Дело в том что мне нужно два алгоритма на эту задачу , один вот он , а вот до другого не могу додуматься , вот вас решил спросить . Мне нужен еще один алгоритм на эту задачу.


Первое: пользуйся тегами...
Второе: будешь продолжать плодить дубликаты - пеняй на себя: темы будут закрываться !!!

Сообщение отредактировано: volvo - 31.05.2005 13:04