<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>

########### Solution 1 DFS ############ 
class Solution(object):
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    res += 1
        return res

    # 渲染：把岛都淹了
    def dfs(self, grid, x, y):
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
            return
        if grid[x][y] == '0':
            return
        
        grid[x][y] = '0'
        # 为什么这里不需要回溯（把grid[x][y]的状态改回来呢？ LC 79
        for i in range(len(dirs)):
            self.dfs(grid, x + dirs[i][0], y + dirs[i][1])

# 或这么写，都可以：【我想说明：其实有点重复性都没有关系的】
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        DIRECTIONS = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        def dfs(grid, x, y):
            if grid[x][y] == "0":
                return

            grid[x][y] = "0"

            for dx, dy in DIRECTIONS:
                nx, ny = x + dx, y + dy
                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
                    dfs(grid, nx, ny)

        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    res += 1
                    dfs(grid, i, j)

        return res
# 或：
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        DIRECTIONS = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        def dfs(grid, x, y):
            
            grid[x][y] = "0"

            for dx, dy in DIRECTIONS:
                nx, ny = x + dx, y + dy
                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == "1":
                    dfs(grid, nx, ny)

        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    res += 1
                    dfs(grid, i, j)

        return res
############ Solution 2 BFS ############ 
# 【更新，推荐写法，可以和下面对比】
# 【最新更新：总结！在哪里加 状态改变，就在哪里检查限制条件！比如这边我选择在入queue的时候加限制条件（检查0 1 ），那么就在入queue之后去改变状态。】可以对比下一个bfs（的更新部分），这个区别就会很明显了。
# 【一定！！！！！】要记得在第一次入queue的时候做检查！！！
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0

        def bfs(start_x, start_y):
            queue = deque([])
            queue.append([start_x, start_y])
            grid[start_x][start_y] = '0'
            dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
            while queue:
                x, y = queue.popleft()
                for direction in dirs:
                    x1 = x + direction[0]
                    y1 = y + direction[1]
                    if not ((0 <= x1 < len(grid)) and (0 <= y1 < len(grid[0]))):
                        continue
                    if grid[x1][y1] != '1':
                        continue
                    queue.append([x1, y1]) 
                    grid[x1][y1] = '0'
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    bfs(i, j)
                    res += 1
        # print(grid)
        return res


# # BFS version 2
# class Solution:
#     def numIslands(self, grid: List[List[str]]) -> int:
#         res = 0

#         def bfs(start_x, start_y):
#             queue = deque([])
#             queue.append([start_x, start_y])
#             dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
#             while queue:
#                 x, y = queue.popleft()
#                 if grid[x][y] == "0": 
#                     continue
#                 grid[x][y] = '0' # 或者使用：visited数组，visited[x][y] = True
#                 for direction in dirs:
#                     x1 = x + direction[0]
#                     y1 = y + direction[1]
#                     if not ((0 <= x1 < len(grid)) and (0 <= y1 < len(grid[0]))):
#                         continue
#                     if grid[x1][y1] != '1':
#                         continue
#                     queue.append([x1, y1]) # 搞清楚x还是x1，这里我很容易出错！！！
#                     # 【更新】其实不是我这下面分析的原因....实际上，在出queue的时候做好【if grid[x][y] == "0": continue】判断就能避免TLE啦！！！！
#                     # grid[x1][y1] = '0' # 【注意！否则会有case TLE】Mark as visited immediately to avoid re-adding to the queue
#         # 【推荐写法】这题的处理特别一些，需要维护的主要状态是第13行。但又多加了第22行是为了这个点不会被重新加入queue中（比如别的点的邻居是这个点），相当于是一个优化。
#         # 【不推荐】如果把需要维护的主要状态设为敌22行，删除第13行，这个例子里还是能过，但这会导致你最后去看grid，grid里可能还有1存在，不利于保持consistency。所以我不推荐！！！
#         for i in range(len(grid)):
#             for j in range(len(grid[0])):
#                 if grid[i][j] == '1':
#                     bfs(i, j)
#                     res += 1
#         # print(grid)
#         return res

############ Solution 3 ############ 
class Solution(object):
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0
        m, n = len(grid), len(grid[0])

        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        dsu = DSU(m * n)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    res += 1
                    
                    for direction in range(len(dirs)):
                        x = i + dirs[direction][0]
                        y = j + dirs[direction][1]
                        if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == '0': # 我之前漏掉了grid[x][y] == '0'!!!
                            continue
                        component1 = dsu.find(i * n + j)
                        component2 = dsu.find(x * n + y)
                        # print(i, j, i * n + j, x, y, x * n + y, component1, component2, res)
                        if (component1 != component2):
                            dsu.union(component1, component2)
                            res -= 1
        return res

class DSU:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
    
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        rootX, rootY = self.find(x), self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX
        

22533