Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of connected free cells that can be reached from the starting position only through the same connection? Can this be done in O(n)?Obviously this can also be formulated as a graph problem, but the board shape imposes restrictions (most significantly: no more than 4 edges per vertex) that may lead to a more efficient algorithm.
How to detect dead ends on a board / in a graph?
ds.algorithms;graph algorithms;planar graphs;board games