# In 2D binary matrix find the number of islands

I am trying to count the number of islands (a group of connected 1s forms an island) in a 2D binary matrix.

Example:

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

In the above matrix there are 5 islands, which are:

``````First: (0,0), (0,1), (1,1), (2,0)
Second: (1,4), (2,3), (2,4)
Third: (4,0)
Fourth: (4,2)
Fifth: (4,4)
``````

To count the number of island in the 2D matrix, I am assuming the matrix as a Graph and then I am using DFS kind of algorithm to count the islands.

I am keeping track for the number of DFS (a recursive function) calls, because that many components would be there in the Graph.

Below is the code I wrote for this purpose:

``````# count the 1's in the island
def count_houses(mat, visited, i, j):
# base case
if i < 0 or i >= len(mat) or j < 0 or j >= len(mat[0]) or\
visited[i][j] is True or mat[i][j] == 0:
return 0
# marking visited at i, j
visited[i][j] = True
# cnt is initialized to 1 coz 1 is found
cnt = 1
# now go in all possible directions (i.e. form 8 branches)
# starting from the left upper corner of i,j and going down to right bottom
# corner of i,j
for r in xrange(i-1, i+2, 1):
for c in xrange(j-1, j+2, 1):
# print 'r:', r
# print 'c:', c
# don't call for i, j
if r != i and c != j:
cnt += count_houses(mat, visited, r, c)
return cnt

def island_count(mat):
houses = list()
clusters = 0
row = len(mat)
col = len(mat[0])
# initialize the visited matrix
visited = [[False for i in xrange(col)] for j in xrange(row)]
# run over matrix, search for 1 and then do dfs when found 1
for i in xrange(row):
for j in xrange(col):
# see if value at i, j is 1 in mat and val at i, j is False in
# visited
if mat[i][j] == 1 and visited[i][j] is False:
clusters += 1
h = count_houses(mat, visited, i, j)
houses.append(h)
print 'clusters:', clusters
return houses

if __name__ == '__main__':
mat = [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
houses = island_count(mat)
print houses
# print 'maximum houses:', max(houses)
``````

I get a wrong output for the matrix I have passed in argument. I get `7` but there are `5` clusters.

I tried debugging the code for any logical errors. But I couldn't find out where is the problem.

big hammer approach, for reference

had to add `structure` argument `np.ones((3,3))` to add diagonal connectivity

``````import numpy as np
from scipy import ndimage

ary = np.array([
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
])

labeled_array, num_features = ndimage.label(ary, np.ones((3,3)))

labeled_array, num_features
Out[183]:
(array([[1, 1, 0, 0, 0],
[0, 1, 0, 0, 2],
[1, 0, 0, 2, 2],
[0, 0, 0, 0, 0],
[3, 0, 4, 0, 5]]), 5)
``````

Your algorithm is almost correct except for the line 21:

``````if r != i and c != j:
cnt += count_houses(mat, visited, r, c)
``````

Instead you want to use `or` as you want to continue counting provided at least one of the coordinate is not the same as your center.

``````if r != i or c != j:
cnt += count_houses(mat, visited, r, c)
``````

An alternate and more intuitive way to write this would be the following

``````if (r, c) != (i, j):
cnt += count_houses(mat, visited, r, c)
``````