CODEWITHSUNDEEP
algorithmlanguage-agnostic
teh internets is made of catz
teh internets is made of catz

Reputation: 1460

Find isolated groups of blocks in a grid

I have a grid of "blocks" (in the form of a 2D array, could be 5*5, 17*17 or whatever) where I can add or remove blocks at will, except for the one at the center that should always remain there.

I can place blocks if they have a local neighbour : on their right/left/up/down (at least one of them).

By removing some blocks, it may leave other blocks isolated with no "connection" to the center-block, and I want to avoid this.

I'm looking for a quick solution to check if all my blocks have a connection to the center, the simplest possible (in terms of coding, I can accept to have a non optimal solution since this is supposed to be on executed on very small data and not so often). The first thing that came to my mind was to implement this as a path search but that seems overkill.

I'm using C++ but that should not make any difference.

Upvotes: 0

Views: 323

Answers (1)

Aravind
Aravind

Reputation: 3179

You need to find the connected components using DFS/BFS.Construct the initial graph and as you add new blocks, you can add new edges, or when you remove blocks you can remove edges.When you remove a block, temporarily delete those edges in the graph and check if it causes two pieces of the graph to disconnect.This is simple, carry out DFS again.If it does not disconnect you can remove that block.

DFS is only about 8 lines to implement, and for small data sets this is elegant.

Upvotes: 1

Related Questions