class Solution(object):

    def numIslands(self, grid):

        """

        :type grid: List[List[str]]

        :rtype: int

        """

        count=0

        m=len(grid)

        if m==0:

            return  0

        n=len(grid[0])

        #visit=[[False]*n]*m

        visit = [[False for i in range(n)]for j in range(m)]

        def check(x, y):

            if x >= 0 and x<m and y>= 0 and y< n and grid[x][y] == '1' and visit[x][y] == False:

                return True

        def dfs(i ,j):

            nbrow = [1,0,-1,0]

            nbcol = [0,1,0,-1]

            for d in range(4):

                ni=i+nbrow[d]

                nj=j+nbcol[d]

                if(check(ni,nj)==True):

                    visit[ni][nj]=True

                    dfs(ni,nj)

        for i in range(m):

            for j in range(n):

                if(check(i,j)==True):

                    visit[i][j]=True

                    dfs(i,j)

                    count+=1

        return count