Count the number of "holes" in a bitmap
algorithm, computer-vision, image-processing, maze
Solution
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.
Problem
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.