C++ Grid gravity simulation opzimization (Kattis Falling Apples)

Question

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 <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;
}

• Sᴀᴍ Onᴇᴌᴀ: Your post has been edited to correct indenation- see code formatting for more information on this topic.

Answer 1

• 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:

  1. Columns are totally independent. Do one column at a time.

  2. Do not drop apples. Count them.

  3. It is beneficial to add an artificial row of obstacles at the bottom.