3 ms·
This is well-studied problem, and trying to make your own solution from scratch you'll often miss the efficient solutions. https://en.wikipedia.org/wiki/Dynami
by o11c 2y ago
This is well-studied problem, and trying to make your own solution from scratch you'll often miss the efficient solutions.
https://en.wikipedia.org/wiki/Dynamic_connectivity https://en.wikipedia.org/wiki/Dynamic_connectivity
To adjust the terminology:
* cells are vertices
* the path between adjacent cells that are both not obstacles are edges
* adding an obstacle means removing all its edges
* removing an obstacle means adding edges for each adjacent cell that isn't also an obstacle
* it's illegal to end up with multiple components (edit: rephrased for correctness) other than obstacles
Personally I've only done the "add edges" direction (which is much simpler).
- xigoi 2y agoAccording to the article, the algorithm for deleting edges runs in amortized O(log n) time, which relies on the fact that if you delete an edge which breaks the graph into two halves (which is the worst-case scenario), the next time you’ll only have half as many vertices in each component. However, the OP is not actually deleting the edges, just checking if deleting them would disconnect the graph. Therefore, unless I’m missing something, the amortization would not work.