Count the number of "holes" in a bitmap
Consider a MxN bitmap where the cells are 0 or 1. '1' means filled and '0' means empty.
Find the number of 'holes' in the bitmap, where a hole is a contiguous region of empty cells.
For example, this has two holes:
11111
10101
10101
11111
... and this has only one:
11111
10001
10101
11111
What is the fastest way, when M and N are both between 1 and 8?
Clarification: diagonals are not considered contiguous, only side-adjacency matters.
Note: I am looking for something that takes advantage of the data format. I know how to transform this into a graph and [BD]FS it but that seems overkill.
Answer
You need to do connected component labeling on your image. You can use the Two-pass algorithm described in the Wikipedia article I linked above. Given the small size of your problem, the One-pass algorithm may suffice.
You could also use BFS/DFS but I'd recommend the above algorithms.