class Solution(object):

     def numIslands(self, grid):

         """

         :type grid: List[List[str]]

         :rtype: int

         """

         m = len(grid)

         if m == 0:

             return 0

         n = len(grid[0])

         ans = 0

         for i in range(m):

             for j in range(n):

                 if grid[i][j] == '':

                     ans += 1

                     self.helper(grid, m, n, i, j)

         return ans

     def helper(self, grid, m, n, i, j):

         if (i < 0 or j < 0 or i > m-1 or j > n-1):

             return 

         if grid[i][j] == '':

             grid[i][j] = ''

             self.helper(grid, m, n, i-1, j)

             self.helper(grid, m, n, i+1, j )

             self.helper(grid, m, n, i, j-1)

             self.helper(grid, m, n, i, j+1)

 class Solution(object):

     def numIslands(self, grid):

         """

         :type grid: List[List[str]]

         :rtype: int

         """

         m = len(grid)

         if m == 0:

             return 0

         n = len(grid[0])

         visited = [ [False]* n for x in range(m)]

         ans = 0

         for i in range(m):

             for j in range(n):

                 if grid[i][j] == '' and visited[i][j] == False:

                     ans += 1

                     self.bfs(grid, visited, m, n, i, j)

         return ans

     def bfs(self, grid, visited, m, n, i, j):

         direct = [[0,1],[0,-1],[1,0],[-1,0]]

         queue = [[i, j]]

         visited[i][j] = True

         while queue:

             front = queue.pop(0)

             for p in direct:

                 np = [front[0]+p[0], front[1]+p[1]]

                 if self.isValid(np, m, n) and grid[np[0]][np[1]] == ''\

                 and visited[np[0]][np[1]] == False:

                     visited[np[0]][np[1]] = True

                     queue.append(np)

     def isValid(self, np, m, n):

         return np[0]>=0 and np[0]<m and np[1]>=0 and np[1]<n