0

I am working on one programming challenge in which I have to find number of zeros surrounded by ones.

I have given:
Number of row and columns r and c
Number of positions of ones n
n positions i j where i is index of row and j is index of column

For example if I have 

011110
010001
010001
001110
000000

then I return 6.
There are 3 test input sets. In the first two sets r, c <= 1000. I managed to pass the first two sets by using DFS to cout number of zeros which are not surrounded by ones (starting from borders). Hence number of zeros z = r * c - k - n where k is number of zeros which are not surrounded by ones.

But in the third case r, c <= 10^18 which doesn't even fit to memory if I create two dimensional vector on beginning. I also noticed that n is relative small in all sets (n <= 10^6).

My question is how to solve this problem for all test sets?

Snip3r
  • 161
  • 2
  • 7
  • "_My question is how to solve this problem for all test sets?_" Simple: by writing code that does that. SO is **not** a code writing service. – Algirdas Preidžius Mar 30 '18 at 12:46
  • 1
    @AlgirdasPreidžius I don't need code for this problem. I am just asking for an algorithm because I haven't been able to devise this algorithm. – Snip3r Mar 30 '18 at 12:53
  • 1) Such question is too broad for SO as well. Once one has the algorithm, it typically can be translated directly into code. So, it's practically the same request. 2) Consider re-taking the [tour], and reading through [ask], and [help]. – Algirdas Preidžius Mar 30 '18 at 12:56
  • One hint: If you have e.g. 10^18 rows and 10^6 ones, then there must be many rows with only zeroes in it. No need to store them in an array. – Ralf Kleberhoff Mar 30 '18 at 13:06
  • All the non-one indices in a row between the first one index and the last one index in the row have zeros that are surrounded by ones. – Mike Borkland Mar 30 '18 at 13:13
  • You could start by implementing a sparse matrix to hold the data (you need to store only the indeces of the non zero values), at least you'll solve the memory problem. – Bob__ Mar 30 '18 at 13:38
  • @Snip3r, just ignore what Algirdas said. There are always people out there trying to act as if they are smarter and more authoritative. You have asked a well defined question and showed your efforts to solve it. I don’t see any problem of asking the question here. – james Mar 30 '18 at 19:22

1 Answers1

0

Counting Rooms While Knowing Where Walls Are here you can find an result of counting the rooms wich are surrounded by walls (in your case "1") you have to change the code, that it counts the number of "0"s. But the idea is the same. Making it via bfs or dfs.

Thomas
  • 2,093
  • 3
  • 21
  • 40
  • This code is for counting the spaces wich are surrounded by walls. If you define the walls as ones, and change the dfs that it counts the zeros, you reach your goal – Thomas Mar 30 '18 at 13:47