I am currently facing an algorithm problem that I can't solve and I really need help with it.
Here's the general layout:
So here's the problem I am facing:
Lets say I have unlocked cells (0,0), (1,0), (2,0), (2,1).
In this situation, locking cell (2,0) should not be possible, since cell (2,1) will lose any connection it has to (0,0).
How can I implement such logic that will make it so cells cannot be locked back, unless it is safe to do so (next cells still have connection to starting point somehow)?
If this requires some general algorithm type, I don't know how to search for it, so feel free to provide me it's name so I can learn it.I didn't study computer science, I'm a self-taught student.
A standard way to do this would be to treat your grid as a graph (a set of vertexes and edges) and view this as a graph problem. The cells would be the vertices of the graph, connected by the horizontal and vertical edges between them. You would keep track of which cells/vertices are unlocked, with the cells bordering unlocked cells being unlockable, and all other cells being locked.
A "cut vertex" or "articulation point" in a graph is a vertex that, if removed, would disconnect the graph. You want to ensure that a cell is not a cut vertex among the unlocked cells before you allow it to be locked (as doing so would disconnect some portion of unlocked cells). You can do a Depth-First-Search over just the unlocked cells to find their articulation points, and check that the cell to be locked is not one of those points before you lock it.