This seems like a... curious problem. I can already see one efficiency for all of this. For each of the visited plots, it can also be re-visited in 2 steps. Therefore, as long as it can be visited in N steps, it can also be visited in N+2, N+4, etc. steps.

What I'm thinking is, instead of the more naieve approach of allowing the computation to repeatedly revisit the same steps over and over, simply mark for each plot how far away it is from the start. THEN, from there, find all plots that are less than 64 steps away AND even. And because of the way movement works, it can be thought of similar to a chess board - even steps are white squares, odd are black; so I have no concerns about a space being both even AND odd from different paths.

struct Step { int x, y, steps; };

vector<string> field;
vector<vector<int>> distances;
queue<Step> steps;

while (!steps.empty())
{
    auto step = steps.front(); steps.pop();

    // Bounds check, rock check, duplicate check
    if (step.x < 0 || step.x >= field.size() || step.y < 0 || step.y >= field[0].size()) continue;
    if (field[step.x][step.y] == '#') continue;
    if (distances[step.x][step.y] >= 0) continue;

    distances[step.x][step.y] = step.steps;

    steps.push(Step{ step.x-1, step.y, step.steps+1 });
    steps.push(Step{ step.x+1, step.y, step.steps+1 });
    steps.push(Step{ step.x, step.y-1, step.steps+1 });
    steps.push(Step{ step.x, step.y+1, step.steps+1 });
}

Okay, now that I'm onto part 2, all the cleverness I thought I had for part 1 just melted away. It's an INFINITE grid with a REDICULOUS number of steps (over 26 million!).

Hmm... I'm realizing that for all but the absolute edge of the grid, the end result for all of the middle iterations will be half of all walkable tiles will be avaliable. And after doing a quick check of both the sample and real input, it's an NxN grid, where N is odd, which means that between two adjacent grids, they will have alternating grid tiles. That means for the interrior tiles, there will be I(W) / 2, where I is the number of interrior grids, and W the number of walkable tiles.

Another neat property by looking at the input is that S is in the exact center, and the row/column that S resides is fully blank - meaning that a path going in each cardinal direction will always have a straight path.

This means I need to figure out:

• The number of fully interior tiles
• The 4 cardinal tips
• The 4 diagonal lines

I figured out the number of repeated fields for the first few iterations (by drawing it out), and the pattern of increase seems to be 2n^2 - 2n + 1. The full number of "interior" tiles will be the number of steps divided by the width of the field (ignoring remainder), plugged into that formula.

For the tips, it's just the map with a starting location at each center edge and a limit based on the remainder ignored previously.

For the lines, it's the map starting at a corner, repeated (M/2) - 1 times.

.... All this math and cleverness and I get the wrong answer. Hrm. Maybe I need to look at this more simply.

I might have a "simpler" way of doing this. I'll just copy out the infinite grid a few times, have it run for a few hundred steps, and show the number walkable tiles on the way. Maybe I can figure out a pattern of growth?

The number of steps is 26501365, which is 202300 * 131, plus 65, with 131 being the width and 65 being half the width. This is all growing quadratically each cycle... so it will grow at the rate of p(x) = ax^2 + bx + c. Basically solve for a, b, and c, then plug in 202300 into the formula to get the result.

• p(0), which equals the result at 65 steps
• p(1), or a + b + c, which will also equal at 131 + 65 steps
• p(2), or 4a + 2b + c, which will also equal at 131 + 131 + 65 steps

Working backwards, solving for a, b, and c:

• c is simply p(0)
• b is (4*p(2) - 3*p(0) - p(2)) / 2
• a is (p(2) + p(1) - p(0) ) / 2