class NumOfInslands: 
    #DFS wrapper, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns
    def numOfIslands(self, mat) :
        m = len(mat)
        n = len(mat[0])
        if mat == None or m == 0 or n == 0:
            return 0
        count = 0;    
        visited = [[False for i in range(n)] for j in range(m)]
        for i in range(0, m):
            for j in range (0, n):
                if mat[i][j] == 1:
                    count+=1
                    self.dfs(mat, i, j, visited)
        return count


    #DFS + memoization, Time O(4) ~ O(1), Space O(1), 4 directions is constant
    def dfs(self, mat, i, j, visited) :
        m = len(mat)
        n = len(mat[0])
        if i < 0 or j < 0 or i > m-1 or j > n-1 or visited[i][j]:
            return
        if mat[i][j] != 1:
            return    
        mat[i][j] = 0
        visited[i][j] = True
        self.dfs(mat, i-1, j, visited); #left
        self.dfs(mat, i+1, j, visited); #right
        self.dfs(mat, i, j-1, visited); #upper
        self.dfs(mat, i, j+1, visited); #lower

matrix = [[0,1,0,1,0],	
          [0,1,0,0,1],
          [0,1,1,0,1]] 
n = NumOfInslands()
print("number of islands: " + str(n.numOfIslands(matrix)))