Problem Statement -

Problem Statement

Given a NxM grid of 1s & 0s (1s mark walls, while 0s indicate empty chambers), the task is to identify the number of chambers & the size of the largest. And just to whet my curiosity, to find in which chamber, a cell belongs.

It seems like an ad hoc problem, since the regular algorithms just don't fit in. I just can't get the logic for writing an algorithm for the problem. If you get it, pseudo-code would be of great help!

Note - I have tried the regular grid search algorithms, but they don't suffice the problem requirements.

Source - INOI Q Paper 2003

  • 1
    "I just can't get the logic for writing an algorithm for the problem" - do you think you could work out the answer, given just the diagram and pen and paper? What would you do? Can you describe that in intricate detail in very simple steps? Voila: an algorithm. – AakashM Dec 17 '12 at 9:37

There is really an off-the-shelf algorithm for this: flood fill

The idea is simply to start a search (DFS or BFS) from any empty space and mark it. If you want to be able to tell the chamber for each cell, you could mark it with a chamber number and a size number, whereas the latter increments during the search. Once the search terminates due to completely filling one chamber, you know its size by the largest size-number written during the search.

You then search for any non-marked and non-wall cells and start a fresh flood fill from there with the next chamber number and size number 1 again.

Your regular grid search algorithm is basically the starting point in order to find free cells for the flood fill algorithm. Once the cells are marked, you simply continue with the same grid search to search a non-marked cell as usual.

The flood fill algorithm takes its name from its early origins in pixel-based paint tools, where it has been the basis for the bucket-fill-tools, which fill an area with the current background color. The wikipedia page linked above contains a nice animated gif to visualize the process. The only adaptations for this problem are that you need to set a size number instead of a color and watch for walls, other than that you can take the pseudocode implementation given on the linked page. But you might as well roll your own, as it is a straightforward search.

It doesn't really matter either if you do a depth-first-search or a breadth-first-search. If you implement DFS (non-tail) recursively and have a huge matrix you might end up in trouble with stack sizes. In that case, the space investment of the BFS might be preferable. Pseudo-code for both variants is given on the wikipedia page.

Note: the wikipedia page already has a nice example on the problem of when there is a 'gap' between chambers. In this problem description, it is not explained properly what a 'connection' is. In other words, from the description you do not know if you should flood 4-way or 8-way, where the latter allows for connections being made through diagonally placed walls, that share a corner, but not an edge. Common sense would dictate a 4-way flood though, as people usually don't consider mathematically point-sized doorways in their castles.

| improve this answer | |
  • note that you can implement DFS (and any recursive algorithm) iterativly – ratchet freak Dec 17 '12 at 7:20
  • Indeed, hence, the if and might. There's no "must be done in this way" of course. – Frank Dec 17 '12 at 9:17

Frank correctly points out one off-the-shelf approach. There is at least one other: disjoint set forests. This may have some benefits, as you can implement a simple data structure and then process the grid in linear order without needing to search for a new starting point.

| improve this answer | |
  • Good point about disjoint sets working as well, though the same grid traversal is needed either way and the set-union seems a bit of an overkill compared to a simple array-cell write. – Frank Dec 17 '12 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.