_1568. Minimum Number of Days to Disconnect Island.md

1568. Minimum Number of Days to Disconnect Island

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 11, 2024

Last updated : August 11, 2024

---

Related Topics : Array, Depth-First Search, Breadth-First Search, Matrix, Strongly Connected Component

Acceptance Rate : 59.4 %

---

Solutions

• h1568.py

Python

h1568.py

class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        def island(i: int, j: int, visited: Set[Tuple[int, int]]) -> None :
            if not (0 <= i < len(grid)) or \
               not (0 <= j < len(grid[0])) or \
               (i, j) in visited or \
               not grid[i][j]:
                return

            visited.add((i, j))
            island(i - 1, j, visited)
            island(i + 1, j, visited)
            island(i, j - 1, visited)
            island(i, j + 1, visited)

        def moreThanOneIsland(x: int, y: int) -> bool :
            islandFnd = False
            visited = set([(x, y)])
            for i in range(len(grid)) :
                for j in range(len(grid[0])) :
                    if grid[i][j] and (i, j) not in visited  :
                        if islandFnd :
                            return True
                        island(i, j, visited)
                        islandFnd = True

            return not islandFnd

        if moreThanOneIsland(-1, -1) :
            return 0

        for i in range(len(grid)) :
            for j in range(len(grid[0])) :
                if grid[i][j] and moreThanOneIsland(i, j) :
                    return 1

        return 2