[anonymoushn]

I'm a competition programmer so my perspective is generally miscalibrated, but part 5 is usually solved with a BFS. You can say BFS is basic, and it's maybe the part of competition programming that comes up more often than any other in real life (tied with sentinels, which you usually use in your BFS?), but I think it's a "data structures" problem.

[josephg]

If this test is calibrated like the triplebyte programming challenges, less than 1% of people will finish part 5 in the time given. I think when I was interviewing, only about 3% of people reached step 5 at all. Finishing was super rare, and it really only existed to separate the top couple percent. (And yes, we told the candidates that we didn’t expect them to finish in the time allocated). It doesn’t matter if step 5 is harder. Most people will never attempt it anyway.

But even then, while BFS would definitely work here, so would DFS and that’s simpler. A simple, unoptimised recursive DFS flood fill would be like 8 lines or something given by that stage you already have a function to reveal a cell. You just have to call it on all the adjacent cells. I don't see that as a data structure problem. You could argue it’s an algorithm problem, but it’s about as easy as those come.

[anonymoushn]

Got me there! The situation where you already have that stuff definitely favors DFS and makes it pretty trivial