C++ в сетке гравитационного моделирования opzimization (Каттис падающих яблок)


У меня есть решение для Каттис падающих яблок проблема (ссылка). Вход представляет собой сетку из Р строк (до 50000) на с колоннами (до 10). У каждого временного шага, яблоки (указывается 'a') переместить вниз на одну ячейку в пустом пространстве (обозначается .) или почивают на препятствие (отмечены #).

Мое решение превышает лимит времени только на последний тест. Я думаю, что цикл while-это проблема, но я понятия не имею, что я могу сделать, чтобы оптимизировать его.

#include <iostream>

using namespace std;

int main()
{
    int r; // Grid rows
    int c; // Grid columns

    scanf("%d %d", &r, &c);

    char grid[r][c];

    // Establish grid
    for (int i = 0; i < r; i++) {
        char line[c];
        scanf("%s", &line);
        for (int j = 0; j < c; j++) {
            grid[i][j] = line[j];
        }
    }

    // Loop to change
    while (true) {
        bool change = false;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {

                if (grid[i][j] == 'a' && grid[i + 1][j] == '.') {
                    grid[i + 1][j] = 'a';
                    grid[i][j] = '.';
                    change = true;
                }

            }
        }

        if (!change) {
            break;
        }
    }

    // Print the grid
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << grid[i][j];
        }
        printf("\n");
    }

    return 0;
}


Комментарии
1 ответ


  • Избежать выделять большие массивы на стеке. По данным ограничения, grid может занять до полутора Мег. Вы опасно близки к переполнению стека.

  • Избежать однобуквенные идентификаторы. Правописание row и col не сделать вашу программу медленнее, но сделало бы его гораздо более читабельным.

  • scanf добавляет нулевой символ в строку. Ваш char line[c] один символ короче. Определенный УБ.

  • В условии задачи четко говорится, что


    Просто повторяя правила гравитации, шаг за шагом, вероятно, слишком долго на больших наборах данных.

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

    Я не хочу называть решение, но вот несколько подсказок:


    1. Колонки полностью независимы. Делать по одному столбцу за раз.

    2. Не бросайте яблоки. Сосчитать их.

    3. Это выгодно добавить искусственный ряд препятствий на дне.


4
ответ дан 31 января 2018 в 08:01 Источник Поделиться