<p>Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>&#39;1&#39;</code>s (land) and <code>&#39;0&#39;</code>s (water), return <em>the number of islands</em>.</p>

<p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>grid[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        n, m = len(grid), len(grid[0])
        count = 0
        moves = [(1,0),
                 (0,1),
                 (-1,0),
                 (0,-1)
        ]
        def helper(x: int, y: int) -> None:
            # if (x,y) in visited:
            #     return 
            for dx, dy in moves:
                if 0 <= x+dx <= n-1 and 0 <= y+dy <= m-1 and grid[x+dx][y+dy] == "1" and (x+dx, y+dy) not in visited:
                    visited.add((x+dx, y+dy))
                    helper(x+dx, y+dy)
            return 
        for x in range(n):
            for y in range(m):
                if (x,y) not in visited and grid[x][y] == "1":
                    helper(x,y)
                    count += 1
                #count += helper(x,y) if (x,y) not in visited and grid[x][y] == 1 else count
        return count
    
    

        




# class Solution:
#     def numIslands(self, grid: List[List[str]]) -> int:
#         m, n = len(grid), len(grid[0])
#         visited = set()
#         dirs = [(1,0),(-1,0),(0,1),(0,-1)]
#         def dfs(x,y):
#             visited.add((x,y))
#             for dx,dy in dirs:
#                 newx,newy = x+dx, y+dy
#                 if 0<=newx<=m-1 and 0<=newy<=n-1 and (newx,newy) not in visited and grid[newx][newy] == "1":
#                     dfs(newx,newy)
#             return
#         res = 0
#         for i in range(m):
#             for j in range(n):
#                 if (i,j) not in visited and grid[i][j] == "1":
#                     dfs(i,j)
#                     res += 1
#         return res







        # m, n = len(grid), len(grid[0])
        # dirs = [(0,1),(1,0),(-1,0),(0,-1)]
        # visited = set()
        # def bfs(node):
        #     queue = deque()
        #     queue.append((node[0],node[1]))
        #     visited.add(node)
        #     while queue:
        #         for i in range(len(queue)):
        #             x,y = queue.popleft()
        #             for dx,dy in dirs:
        #                 if 0<=x+dx<=m-1 and 0<=y+dy<=n-1 and grid[x+dx][y+dy] == '1' and (x+dx,y+dy) not in visited:
        #                     visited.add((x+dx,y+dy))
        #                     queue.append((x+dx,y+dy))
        #     return 1
        # total = 0
        # for i in range(m):
        #     for j in range(n):
        #         if grid[i][j] == "1" and (i,j) not in visited:
        #             total += bfs((i,j))
        # return total



        
27038