Условие задачи:
В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1 х 1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 30000). Размеры пола m х n. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.
Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек.
Входные данные:
Первая строка содержит числа m и n – размеры пола (1 ≤ m, n ≤ 100). Далее идет m строк, начиная сверху, в каждой из которых размещено n чисел – количество зернышек на соответствующей плитке.
Выходные данные:
Вывести маршрут движения мышки в формате: RRFFFRF (F – шаг вперед, R – шаг вправо).
Тесты:
| Входные данные | Выходные данные |
| 2 3 3 2 4 1 5 1 |
RFR |
| 4 4 34 5 7 8 7 8 9 23 1 2 909 54 3 4 8 0 |
RRFRFF |
| 7 8 23 4 7 8 94 23 5 6 2 9 7 56 83 5 44 2 1 2 3 4 5 6 7 8 8 7 6 5 4 32 2 1 90 87 3 5 4 3 2 5 28 75 60 94 33 3 2 7 76 92000 402 28 3 2 11 200 |
RFRRFFFFRFRRR |
Код на С++:
|
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 |
#include <iostream> #include <algorithm> #include <string> using namespace std; int main() { int m,n; long long X[100][100]; string ans; cin>>n>>m; for (int i=n-1; i>=0; i--){ for (int j=0; j<m; j++)cin>>X[i][j]; } for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0]; for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1]; for (int i=1; i<n; i++){ for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]); } int k=n-1, t=m-1; while (k>0 || t>0){ if (k>0 && t>0){ if (X[k-1][t]>X[k][t-1]){ ans+="F"; k--; } else{ ans+="R"; t--; } } else if (k==0){ ans+="R"; t--; } else if (t==0){ ans+="F"; k--; } } reverse(ans.begin(),ans.end()); cout<<ans; return 0; } |
Код на Java:
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n=in.nextInt(); int m=in.nextInt(); long[][] X = new long[100][100]; String ans = new String(""); for (int i=n-1; i>=0; i--){ for (int j=0; j<m; j++)X[i][j]=in.nextLong(); } for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0]; for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1]; for (int i=1; i<n; i++){ for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]); } int k=n-1, t=m-1; while (k>0 || t>0){ if (k>0 && t>0){ if (X[k-1][t]>X[k][t-1]){ ans+="F"; k--; } else{ ans+="R"; t--; } } else if (k==0){ ans+="R"; t--; } else if (t==0){ ans+="F"; k--; } } String reverse = new StringBuffer(ans).reverse().toString(); System.out.println(reverse); } } |
Описание решения задачи:
Представим пол индийского храма в виде двумерного массива. Т.к по условию движение мышки начинается с левого нижнего угла, при заполнении произойдет сдвиг, где позиция с изначальным номером [latex][n-1][0][/latex] примет позицию под номером [latex][0][0][/latex] и так далее пока данный сдвиг не достигнет плитки с номером [latex][n-1][0][/latex], где станет клеткой [latex][n-1][m-1][/latex]. Далее с помощью обхода в несколько циклов пересчитаем ячейки массива [latex]X[/latex] так, чтобы [latex]X[i][j][/latex] содержало максимальное количество зернышек, которое можно собрать по достижении плитки [latex](i, j)[/latex]. Переместимся в конец массива, в позицию под номером [latex]X[n-1][m-1][/latex]. Двигаясь в начальную клетку по закону, что предыдущая клетка слева или снизу должна содержать максимальное количество зернышек из всех возможных путей мыши, записываем в строку соответствующую букву, которая указывает на сделанный ход. По достижению цели мы получаем строку почти с готовым ответом. Перевернем ее, и теперь она указывает правильный путь не с конца в начало, а с начала в конец, что и требовалось. Выведем ответ.
Код задачи на с++
Код задачи на Java
Засчитанное решение на C++
Засчитанное решение на Java
Можно использовать отображение map: