This seems like an interesting sort of breadth-first search. Basically, keep queuing up tiles/directions to check out, splitting on splitters, until no more beams move. It would probably make more sense to track the results seprately rather than mutating the input.
struct BeamStep { int x, y; char dir; };
vector<string> room;
vector<vector<bool>> energized;
queue<BeamStep> queue;
while (!queue.empty())
{
auto step = queue.front(); queue.pop();
// Ignore if it would go off of the grid
if (step.x < 0 || step.x >= room.size() || step.y < 0 || step.y >= room[0].size()) continue;
energized[step.x][step.y] = true;
int nextX = step.x, nextY = step.y;
char nextDir = step.dir;
switch (room[step.x][step.y])
{
case '.':
switch (step.dir)
{
case 'u': nextX -= 1; break;
case 'd': nextX += 1; break;
case 'l': nextY -= 1; break;
case 'r': nextY += 1; break;
}
queue.push(BeamStep{ nextX, nextY, step.dir });
continue;
case '\\': // reflect logic
case '/': // reflect logic
case '-': // split logic
case '|': // split logic
}
}
This works... but it never finishes on the example input. Running it for a bit while visualizing it, I'm realizing that it has an infinite loops. It's just going around in a big circle around the room!
Simply marking which tiles have been visited isn't enough. I need to mark which direction the beam was facing so I don't repeat it.
struct Dir
{
bool u, d, l, r;
bool energized() { return u || d || l || r; }
};
vector<vector<Dir>> energized;
// ...
switch (step.dir)
{
case 'u': if (energized[step.x][step.y].u) continue; energized[step.x][step.y].u = true; break;
case 'd': if (energized[step.x][step.y].d) continue; energized[step.x][step.y].d = true; break;
case 'l': if (energized[step.x][step.y].l) continue; energized[step.x][step.y].l = true; break;
case 'r': if (energized[step.x][step.y].r) continue; energized[step.x][step.y].r = true; break;
}
I know, kinda ugly to one-line it like that. But it helps to reduce copy-paste errors by having it all aligned like that. And this works to get rid of the loops!
This makes sense; check every direction you can start from, and get the greatest output of it all. Not a big deal, just run this again for every edge tile. Just pop the main logic of this into a function, run it for all of the edge tiles, and return the greatest result.
int maxEnergized = 0;
// Top & Bottom
for (int i = 0; i < room[0].size(); i++)
{
maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{0, i, 'd'}));
maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{(int)room.size()-1, i, 'u'}));
}
// Left & Right
for (int i = 0; i < room.size(); i++)
{
maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{i, 0, 'r'}));
maxEnergized = max(maxEnergized, GetEnergizedCount(room, BeamStep{i, (int)room[0].size()-1, 'r'}));
}