C++ Grid gravity simulation opzimization (Kattis Falling Apples) I have a solution for the Kattis Falling Apples problem (link).  The input is a grid of R rows (up to 50000) by C columns (up to 10).  At each timestep, apples (indicated by 'a') move down one cell into an empty space (denoted by .) or rest upon an obstacle (marked by #).

My solution exceeds time limit only at the last test case.  I'm thinking the while loop is the problem, but I have no idea what I could do to optimize it.

#include &lt;iostream&gt;

using namespace std;

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

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

    char grid[r][c];

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

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

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

                if (grid[i][j] == 'a' &amp;&amp; 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 &lt; r; i++) {
        for (int j = 0; j &lt; c; j++) {
            cout &lt;&lt; grid[i][j];
        }
        printf("\n");
    }

    return 0;
}
Avoid allocating large arrays on a stack. According to the restrictions, grid may take up to half a meg. You are dangerously close to stack overflow.
Avoid single letter identifiers. Spelling out row and col wouldn't make your program any slower, but it would make it much more readable.
scanf adds a null terminator to a string. Your char line[c] is one character short. Definite UB.
The problem statement clearly says that


  Merely iterating the gravity rule, a step at a time, will likely take too long on large datasets.


but that is exactly what your code is doing. No optimization may salvage this algorithm. You need to rethink the approach.

I don't want to spell out a solution, but here are few hints:


Columns are totally independent. Do one column at a time.
Do not drop apples. Count them.
It is beneficial to add an artificial row of obstacles at the bottom.