Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
0 / 0 / 0
Регистрация: 20.06.2014
Сообщений: 4
1

Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек

06.03.2015, 14:19. Показов 1003. Ответов 2
Метки нет (Все метки)

В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1х1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 30000). Размеры пола mхn. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.

Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек.


Технические условия
Входные данные

Первая строка содержит числа m и n – размеры пола (1 ≤ m, n ≤ 100). Далее идет m строк, начиная сверху, в каждой из которых размещено n чисел – количество зернышек на соответствующей плитке.

Выходные данные

Вывести маршрут движения мышки в формате: RRFFFRF (F – шаг вперед, R – шаг вправо).

Добавлено через 1 час 5 минут
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var 
m,n,i,j:integer;
a:array[1..100,1..100] of integer;
begin
readln(m,n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);
 
i:=m;
j:=1;
 
While (i>1) or (j<n) do
  begin
    if (i=1) and (j<n) then begin Write('R'); j:=j+1; end
    else if (i>1) and (j=n) then begin Write('F'); i:=i-1; end
    else
      begin
        if a[i-1,j]>=a[i,j+1] then begin Write('F'); i:=i-1; end
        else begin Write('R'); j:=j+1; end;        
      end;      
  end;
end.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.03.2015, 14:19
Ответы с готовыми решениями:

Напишите программу, которая находит наибольшее количество монет, которое может собрать пират, и выводит его маршрут
Прямоугольный остров разделён на квадраты, так что его размеры – N на M квадратов. В каждом...

Найти наибольшее возможное значение суммы и маршрут, на котором достигается эта сумма
В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке...

Найти наибольшее возможное значение суммы и маршрут, на котором достигается эта сумма
Добрый вечер. Не понимаю вообще как решить. Прошу помочь. В левом верхнем углу прямоугольной...

Массив: Последнее дело Оушена. Составьте маршрут, следуя которому, Оушен успеет ограбить все банки.
Оушен отправляется на пенсию! Но для обеспечения безбедной старости он решил напоследок ограбить n...

2
1643 / 1072 / 1081
Регистрация: 03.07.2013
Сообщений: 4,507
06.03.2015, 16:45 2
Цитата Сообщение от OneD Посмотреть сообщение
if a[i-1,j]>=a[i,j+1]
Этот алгоритм не правильный.
Вот пример поля:
3 1 1 1
2 1 1 9
4 1 1 9
0 1 9 9

По Вашем алгоритму мышка соберет 4+2+3+1+1+1 = 12
А по правильному алгоритму: 1+9+9+9+9+1 = 38

Добавлено через 1 час 33 минуты
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Var
  m,n,i,j : Byte;
  a       : array[1..100,1..100] of Integer;
  s       : String :='';
 
Function Path(r,c : Byte; Var st : String) : Integer;
Var pR,pF : Integer;
sR,sF : String;
Begin
  Path:=0;
  If (r=1) and (c=n)  then Path:=a[r,c]
  else
    Begin
      If c<n then pR:=Path(r,c+1,sR) else pR:=-1;
      If r>1 then pF:=Path(r-1,c,sF) else pF:=-1;
      If (pR>=0) and (pR>=pF) then
      Begin
        Path:=a[r,c]+pR;
        St:='R'+sR;
      end;
      If (pF>=0) and (pF>pR) then
      Begin
        Path:=a[r,c]+pF;
        St:='F'+sF;
      end;
    end;
end;
 
Begin
  m:=10; n:=10; {Readln(m,n);}
  For i:=1 to m do
   For j:=1 to n do
   Begin
     a[i,j]:=Random(10);
     Write(a[i,j]:3);
     If j=n then Writeln;
   end;
  Writeln(#13,Path(m,1,s),' '+s);
end.
2
Модератор
Эксперт по электронике
7664 / 3827 / 1484
Регистрация: 01.02.2015
Сообщений: 11,837
Записей в блоге: 2
07.03.2015, 14:48 3
А можно ещё одним способом - смесью bfs и алгоритма Дейкстры. Должно быть быстрее за счёт сохранения оптимальной предистории и сокращения вариантов перебора. Правда исходник разрастётся.

Добавлено через 16 часов 11 минут
Например так
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
program Mouse;
 
const
  Mmax = 100;
  Nmax = 100;
  Kmax = 30000;
var
  m, n: integer;
  floor: array of array of DWord; //"пол" в храме
  grain: array of array of DWord; //максимальное количество зёрен при прохождении к ячейке
  prev: array of array of char;   //в символьном виде указывает предыдущую плитку в маршруте
  WaveI, WaveJ: array of array of integer; //список ячеек для текущего и следующего прохода
  WaveL: array [0..1] of integer; //длины списков текущего и следующего проходов
  WaveN, WaveNnext: integer;      //индексы списков текущего и следующего проходов
  i, j: integer;
  ii, jj: integer;
  s: string;
begin
  Assign(input, 'mouse.in');
  reset(input);
  readln(m, n);
  SetLength(floor, m, n);
  SetLength(grain, m, n);
  SetLength(prev, m, n);
  SetLength(WaveI, 2, m + n);
  SetLength(WaveJ, 2, m + n);
  for i := 1 to m do
  begin
    for j := 1 to n do
    begin
      Read(floor[i - 1, j - 1]);
      grain[i - 1, j - 1] := 0;
    end;
    readln;
  end;
  
  WaveN := 0;
  WaveL[WaveN] := 0;
  WaveI[WaveN][WaveL[WaveN]] := n - 1;
  WaveJ[WaveN][WaveL[WaveN]] := 0;
  Inc(WaveL[WaveN]);
  grain[n - 1, 0] := floor[n - 1, 0];
  prev[n - 1, 0]  := 'S';
  while WaveL[WaveN] > 0 do
  begin
    WaveNnext := (WaveN + 1) mod 2;
    WaveL[WaveNnext] := 0;
    for i := 0 to WaveL[WaveN] - 1 do
    begin
      ii := WaveI[WaveN][i];
      jj := WaveJ[WaveN][i];
      if ii < n - 1 then
      begin
        if grain[ii, jj] < grain[ii + 1, jj] + floor[ii, jj] then
        begin
          prev[ii, jj]  := 'F';
          grain[ii, jj] := grain[ii + 1, jj] + floor[ii, jj];
        end;
      end;
      if jj > 0 then
      begin
        if grain[ii, jj] < grain[ii, jj - 1] + floor[ii, jj] then
        begin
          prev[ii, jj]  := 'R';
          grain[ii, jj] := grain[ii, jj - 1] + floor[ii, jj];
        end;
      end;
      if ii > 0 then
      begin
        WaveI[WaveNnext][WaveL[WaveNnext]] := ii - 1;
        WaveJ[WaveNnext][WaveL[WaveNnext]] := jj;
        Inc(WaveL[WaveNnext]);
      end;
      if (jj < n - 1) and (ii = n - 1) then
      begin
        WaveI[WaveNnext][WaveL[WaveNnext]] := ii;
        WaveJ[WaveNnext][WaveL[WaveNnext]] := jj + 1;
        Inc(WaveL[WaveNnext]);
        grain[ii, jj + 1] := grain[ii, jj] + floor[ii, jj + 1];
        prev[ii, jj + 1]  := 'R';
      end;
    end;
    WaveN := WaveNnext;
  end;
  {восстановление пути}
  SetLength(s, n + m - 2);
  ii := 0;
  jj := n - 1;
  for i := n + m - 2 downto 1 do
  begin
    s[i] := prev[ii, jj];
    if s[i] = 'F' then
      ii := ii + 1
    else
      jj := jj - 1;
  end;
  writeln(s);
  Close(input);
end.
Здесь реализовано подобие волнового алгоритма (разновидность bfs). Переключение между текущей и предыдущей волнами по переменной WaveN - чтобы избежать длительного копирования массивов. Это подобие "очереди", сейчас мне кажется, что можно было обойтись одной общей очередью.
В grain хранится максимально возможное количество зерен, при перемещении из начальной клетки в grain[i,j].
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.03.2015, 14:48

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

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.