title: In 2D binary matrix find the number of islands
body: <p>I am trying to count the number of islands (a group of connected 1s forms an island) in a 2D binary matrix.</p>
  
  <p>Example:</p>
  
  <pre><code>[
  [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]
  ]
  </code></pre>
  
  <p>In the above matrix there are 5 islands, which are:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>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.</p>
  
  <p>I am keeping track for the number of DFS (a recursive function) calls, because that many components would be there in the Graph.</p>
  
  <p>Below is the code I wrote for this purpose:</p>
  
  <pre><code># count the 1's in the island
  def count_houses(mat, visited, i, j):
      # base case
      if i &lt; 0 or i &gt;= len(mat) or j &lt; 0 or j &gt;= 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)
  </code></pre>
  
  <p>I get a wrong output for the matrix I have passed in argument. I get <code>7</code> but there are <code>5</code> clusters.</p>
  
  <p>I tried debugging the code for any logical errors. But I couldn't find out where is the problem.</p>