Okay this one doesn't seem TOO bad, at first glance.

1. A preprocessing step to add extra space
2. Counting each pair distance

The second one might be a little tricky just to make sure it's not double counting pairs (eg. counting the pair (1,2) AND (2,1)), but that's not that bad.

// Add rows
for (int i = 0; i < galaxy.size(); i++)
{
    if (galaxy[i].find("#") == string::npos)
    {
        galaxy.insert(galaxy.begin()+i, galaxy[i]);
        i++;
    }
}

// Add columns
for (int j = 0; j < galaxy[0].size(); j++)
{
    bool isEmpty = true;
    for (int i = 0; i < galaxy.size(); i++)
    {
        if (galaxy[i][j] == '#')
        {
            isEmpty = false;
            break;
        }
    }

    if (!isEmpty) continue;

    for (int i = 0; i < galaxy.size(); i++)
    {
        galaxy[i].insert(galaxy[i].begin()+j, '.');
    }
    j++;
}

Don't know if there's a more elegant way to do it, but it works. Just need to compute the Manhattan distance for each pair...

// Find and mark galaxies
vector<pair<int, int>> galaxies;
for (int x = 0; x < universe.size(); x++)
{
    for (int y = 0; y < universe[x].size(); y++)
    {
        if (universe[x][y] == '#') galaxies.push_back(pair<int, int>(x, y));
    }
}

// Get paired distances
uint64_t distanceSum = 0;
for (int i = 0; i < galaxies.size(); i++)
{
    for (int j = i+1; j < galaxies.size(); j++)
    {
        distanceSum += abs(galaxies[i].first - galaxies[j].first) + abs(galaxies[i].second - galaxies[j].second);
    }
}

Ugh... a complication. Now instead of one row, it's one MILLION rows. The example they gave led everyone to add space via just expanding an array. What a gotcha.

I think the solution may be relatively simple though: just mark where the expansions would be, and whenever coordinates or distances need to be referenced, just check where the expansion rows/columns would be. I really only need to do this for the "find and mark galaxies" step, as I'm just calculating distances from the coordinates there, as well as the parsing code to mark these lines. The distance code should still work as-is.

int64_t INFLATION_SIZE = 1000000 - 1; // -1 to account for existing single row
vector<int64_t> expandRows;
vector<int64_t> expandCols;

pair<int64_t, int64_t> getExpandedCoords(int x, int y)
{
    pair<int64_t, int64_t> expanded = pair<int64_t, int64_t>(x, y);

    for (auto row: expandRows)
    {
        if (x >= row) expanded.first += INFLATION_SIZE;
    }

    for (auto col: expandCols)
    {
        if (y >= col) expanded.second += INFLATION_SIZE;
    }

    return expanded;
}

And it works!