2

Identifying 0's that are completely surrounded by 1's (doesn't need diagonal coverage). In the example below, the size should be 3.

There could be any number of "holes" in the 2D array.

[[1,0,1,1],
 [1,1,1,1],
 [1,0,0,1],
 [1,0,1,1],
 [1,1,1,0]]

Note: I see the question here: Finding holes in 2d point sets?, but I'm not very satisfied with the answers there.

Community
  • 1
  • 1
yifanwu
  • 1,595
  • 3
  • 14
  • 25
  • how is it 3 in this example? – user2963623 Jul 30 '14 at 06:25
  • What do you mean by "doesn't need diagonal coverage"? the holes can be irregular in shape. How do you decide which is the diagonal cell? – Abhishek Bansal Jul 30 '14 at 06:32
  • @yifanwu what is size? hole zeros count? or perimeter size or bounding box biggest size or what exactly? btw that linked question is not the same as yours it is for huge datasets with points not exactly on grid like in matrix instead with finite accuracy as float coordinates of real measurement! – Spektre Jul 30 '14 at 06:56

2 Answers2

3

Your "holes" are actually connected components of zeroes within a graph formed by the grid. Each element has four neighbours. Find connected components with BFS or DFS, pick the largest one, or sum them up. This algorithm works in O(N), where N is the number of elements in the matrix.

You can also use more specific labeling algorithm, that works on these types of graphs, usually appearing from images. Labeling will also enumerate all the connected components for you.

If you are not interested in connected components, that are not completely surrounded by ones, like this:

[[1,0,1,1],
 [1,1,1,1],
 [1,0,0,1],
 [0,0,1,1],  // <-- Note zero in the beginning
 [1,1,1,0]]

You can expand your matrix with border of zeros, like this:

[[0,0,0,0,0,0]
 [0,1,0,1,1,0],
 [0,1,1,1,1,0],
 [0,1,0,0,1,0],
 [0,0,0,1,1,0],
 [0,1,1,1,0,0],
 [0,0,0,0,0,0]]

And then ignore the outer connected component. In this example, there are no more components, so the answer is zero.

Mikhail
  • 20,685
  • 7
  • 70
  • 146
0

You can use simple DFS to find a hole as follows :-

  1. Do DFS on unvisited node if it is a 0
  2. Terminate DFS if you reach 1 or boundary.
  3. Set a variable say boundary_hit = true if boundary is hit.
  4. count the zero elements visited during DFS.
  5. But if boundary_hit = true then it cannot be a hole
  6. Update max_size with new count only if there boundary_hit = false.
Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19