CODEWITHSUNDEEP
algorithm
yifanwu
yifanwu

Reputation: 1645

given a 2d array, find the "holes"

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.

Upvotes: 2

Views: 3829

Answers (2)

Mikhail
Mikhail

Reputation: 21769

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.

Upvotes: 3

Vikram Bhat
Vikram Bhat

Reputation: 6246

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.

Upvotes: 0

Related Questions