Мышка и зернышки C++

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

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

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

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

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

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

			#include "iostream"
using namespace std;
#define SIZE 100
long long mas[SIZE][SIZE], n, m, x, y;
char tmp;
int main()
{
    cin >> n >> m;
    for (int i = n-1; i >= 0; i--)
    {
        for (int j = 0; j < m; j++) cin >> mas[i][j];
    }

    for (int i = 1; i < n; i++) mas[i][0] += mas[i - 1][0];
    for (int j = 1; j < m; j++) mas[0][j] += mas[0][j - 1];

    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++) mas[i][j] += max(mas[i - 1][j], mas[i][j - 1]);

    x = n - 1; y = m - 1;
    while (x != 0 || y != 0)
    {
        mas[x][y] = -1;
        if (x > 0 && y > 0)
        {
            if (mas[x - 1][y] > mas[x][y - 1]) x--;
            else y--;
        }
        else if (x == 0) y--;
        else if (y == 0) x--;
    }
    mas[0][0] = -1;
    x = y = 0;
    while (x != n-1 || y != m-1)
    {
        if (x < n - 1 && mas[x + 1][y] == -1) { cout << "F"; x++; }
        else { cout << "R"; y++; }
    }
    cout << endl;
}
Назад

Повышение продаж с помощью веб-форм Разложение числа на простые множители Как качественный контент способствует продвижению сайта Как выбрать хостинг Как писать SEO-тексты? Что такое SEO оптимизация сайта


Хостинг

Есть решение которого нет на сайте? Пиши admin@devexe.top