islands = []
explored_points = {}


class Solution:
    def check_valid(self, grid, i, j):
        num_rows = len(grid)
        num_columns = len(grid[0])
        if int(i) < 0 or int(i) >= num_rows:
            return False
        if int(j) < 0 or int(j) >= num_columns:
            return False
        return True

    # assumes grid[i][j]==1
    def explore_islands(self, grid, i, j, starting_i, starting_j, current_stack={}):
        global explored_points
        global islands
        if self.check_valid(grid, i, j-1) and not(explored_points.get('{}{}'.format(i, j-1), None)):
            if grid[i][j-1] == '1':
                current_stack['{}{}'.format(i, j-1)] = 1
                explored_points['{}{}'.format(i, j-1)] = 1
                current_stack = self.explore_islands(
                    grid, i, j-1, starting_i, starting_j, current_stack=current_stack
                )
        if self.check_valid(grid, i, j+1) and not(explored_points.get('{}{}'.format(i, j+1), None)):
            if grid[i][j+1] == '1':
                current_stack['{}{}'.format(i, j+1)] = 1
                explored_points['{}{}'.format(i, j+1)] = 1
                current_stack = self.explore_islands(
                    grid, i, j+1, starting_i, starting_j, current_stack=current_stack
                )
        if self.check_valid(grid, i-1, j) and not(explored_points.get('{}{}'.format(i-1, j), None)):
            if grid[i-1][j] == '1':
                current_stack['{}{}'.format(i-1, j)] = 1
                explored_points['{}{}'.format(i-1, j)] = 1
                current_stack = self.explore_islands(
                    grid, i-1, j, starting_i, starting_j, current_stack=current_stack
                )
        if self.check_valid(grid, i+1, j) and not(explored_points.get('{}{}'.format(i+1, j), None)):
            if grid[i+1][j] == '1':
                current_stack['{}{}'.format(i+1, j)] = 1
                explored_points['{}{}'.format(i+1, j)] = 1
                current_stack = self.explore_islands(
                    grid, i+1, j, starting_i, starting_j, current_stack=current_stack
                )
        # following is the starting point, reached after exploring all the neighbours
        if starting_i == i and starting_j == j:
            islands.append(current_stack)
            return
        return current_stack

    def numIslands(self, grid) -> int:
        global islands
        global explored_points
        for row in range(len(grid)):
            for column in range(len(grid[row])):
                # print('Checking {} row and {} column'.format(row, column))
                if ((not explored_points.get('{}{}'.format(row, column), None)) and (grid[row][column] == '1')):
                    explored_points['{}{}'.format(row, column)] = 1
                    self.explore_islands(grid, row, column, row, column, current_stack={
                                         '{}{}'.format(row, column): 1})
        return(len(islands))


solution = Solution()
# print(solution.numIslands(
#     [["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], [
#         "1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"]]
# ))
print(solution.numIslands([]))