This seems mostly like a weighted pathfinding algorithm, but seemingly with a caveat that no line can be more than 3 long. This is going to be a bit annoying to deal with, but not wholly awful if I can just encapsulate the whole state of the crucible (including how many straight moves) properly.

struct StepState
{
    int x, y, heat, straights;
    char lastDir;
};

struct CompareState {
    bool operator()(StepState const& s1, StepState const& s2) { return s1.heat > s2.heat; }
};

If I use a priority queue, and only use the lowest waiting state, it should eventually reach the end tile with the lowest state. And likely a "visited" grid to make sure any city block isn't potentially visited twice. Any path from there is going to be the same, but the first time it's visited will be at the lowest starting heat state to reach there anyway.

... excpet after working for nearly an hour, I've just noticed a MAJOR flaw in my reasoning. Because of the 'at most 3 straight' rule, it isn't as simple as 'lowest heat at a space', as there might be a lower-heat path it can't take!

I'll admit, I was stubborn when implementing this. I should have been considering that search states are more complex, and consist of x and y positions, the straight counter, and direction. If I considered that when testing if I had seen a state before, then it would have worked so much earlier.

set<tuple<int, int, int, char>> visited;

while (!queue.empty())
{
    auto state = queue.top(); queue.pop();

    if (visited.find({state.x, state.y, state.straights, state.lastDir}) != visited.end())
        continue;
    visited.insert({state.x, state.y, state.straights, state.lastDir});

    // Next states logic...
}

I admit, it took a few minutes to run. Something is wonky with my code but I don't know what. But it gave the right answer.

Hmm. This makes things more complicated, but not TOO much more complicated. Essentially, instead of path segments of length 1-3, it's now from 4-10. A few tweaks to the code should allow for this, particularly the 'minimum' amount, but it should just be a few extra state.straights checks.

if (state.straights < 10)
{
    // Handle moving straight...
}

if (state.straights >= 4)
{
    // Handle turning...
}

Just that one change, wrapping turning in the conditing and changing the moving straight condition, and it just immediately worked. Also, checking the end condition to make sure the straight segment is at least 4. Almost didn't recognize that too. Whoops.

Anyway, this took about 20 minutes to run this time. I realized just as it finished that the issue was simply that checking the set was taking FAR too long. Using a series of maps may have been a better idea. Next time.