Skip to content

Small island problem

There are many island questions on LeetCode. Although there is no official label, they are similar to me. Both the ideas and routines are similar, and you can combine them to practice.

To put it loosely, the island issue is a subtopic of DFS.

Routine

The routines for this problem are all DFS, and you can start with one or more DFS entries. For DFS, we can extend it in four directions.

One of the most classic code templates:

seen = set()
def dfs(i, j):
  if i is out of bounds or j is out of bounds: return
  if (i, j) in seen: return
  temp = board[i][j]
  # Mark as visited
  seen.add((i, j))
  # On
  dfs(i + 1, j)
  # Next
  dfs(i-1, j)
  # Right
  dfs(i, j + 1)
  # left
  dfs(i, j-1)
  # Unmark
  seen.remove((i, j))
# Single point search
dfs(0, 0)
# Multipoint search
for i in range(M):
   for j in range(N):
      dfs(i, j)

Sometimes we can even mark the access status of each cell without visiting, but mark it in place directly. The space complexity of this algorithm will be better. This is also a very common technique, everyone must master it proficiently.

def dfs(i, j):
  if i is out of bounds or j is out of bounds: return
  if board[i][j] == -1: return
  temp = board[i][j]
  # Mark as visited
  board[i][j] = -1
  # On
  dfs(i + 1, j)
  # Next
  dfs(i-1, j)
  # Right
  dfs(i, j + 1)
  # left
  dfs(i, j-1)
  # Unmark
  board[i][j] = temp
# Single point search
dfs(0, 0)
# Multipoint search
for i in range(M):
   for j in range(N):
      dfs(i, j)

The above four questions can all be done using regular DFS. And the directions of recursion are all four directions up, down, left, and right. What's more interesting is that in-situ modifications can be used to reduce the space for visiting.

Among the 463 questions, when doing DFS, you need to pay attention to the length of each adjacent side may be double-calculated, so it needs to be subtracted. My idea here is:

-Add 4 to land -Continue to determine whether it is land on the left and above -If it is, there will be double counting, this time the double counting is 2, so just subtract 2 -If not, the calculation will not be repeated, just ignore it

Note that you don't need to forget the ones on the right and bottom, otherwise the calculation will be repeated.

Code:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if i <0 or i >= m or j <0 or j >= n or grid[i][j] != 1:
                return 0
            grid[i][j] = -1
            ans = 4 + dfs(i + 1, j) + dfs(i-1, j) + \
                dfs(i, j + 1) + dfs(i, j-1)
            if i> 0 and grid[i-1][j] != 0:
                ans -= 2
            if j> 0 and grid[i][j-1] != 0:
                ans -= 2
            return ans

        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j)

Of course, if you choose to judge the right and the bottom are the same, you only need to change the two lines of code, there is no difference between the two algorithms. Code:

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        def dfs(i, j):
            if i <0 or i >= m or j <0 or j >= n or grid[i][j] != 1:
                return 0
            grid[i][j] = -1
            ans = 4 + dfs(i + 1, j) + dfs(i-1, j) + \
                dfs(i, j + 1) + dfs(i, j-1)
            # Need to change here
            if i <m-1 and grid[i + 1][j] != 0:
                ans -= 2
            # Need to change here
            if j <n-1 and grid[i][j + 1] != 0:
                ans -= 2
            return ans

        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i, j)

If you encounter a small island problem next time, or can be abstracted as a small island model problem, you can try to use the template introduced to you in this section. The regularity of this topic is very strong, similar to the stone game, most of the stone game can be done with DP, which is a kind of routine.

Extension

In fact, many questions have the shadow of small island questions. The core of the so-called small island questions is to find connected regions. If you can turn the problem into finding connected regions, then you can use the ideas in this section to do it. For example 959. Divide regions by slashes

Title description:

In an N x N grid consisting of 1 x 1 squares, each 1 x 1 square is composed of /, \ or spaces. These characters divide the square into co-sided areas.

(Please note that the backslash character is escaped, so \ is represented by "\\".).

Returns the number of regions.

Example 1:

enter:
[
  "/",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:


Example 2:

enter:
[
  "/",
  ""
]
Output: 1
Explanation: The 2x2 grid is as follows:


Example 3:

enter:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because the \ character is escaped, "\\/" means \/, and "/\\" means /\.)
The 2x2 grid is as follows:


Example 4:

enter:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because the \ character is escaped, "/\\" means /\, and "\\/" means \/.)
The 2x2 grid is as follows:


Example 5:

enter:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:


prompt:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is'/','\', or ''.

In fact, if you convert the "/" and "\" in the title into a 3 x 3 grid, the problem becomes the number of connected regions, which can be solved using the ideas in this section . I leave it to the reader to think about it. Here I will post a Python3 code for everyone.

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        m, n = len(grid), len(grid[0])
        new_grid = [[0 for _ in range(3 * n)] for _ in range(3 * m)]
        ans = 0
        # Preprocessing, generate a new 3 * m * 3 * n grid
        for i in range(m):
            for j in range(n):
                if grid[i][j] =='/':
                    new_grid[3 * i][3 * j + 2] = 1
                    new_grid[3 * i + 1][3 * j + 1] = 1
                    new_grid[3 * i + 2][3 * j] = 1
                if grid[i][j] =='\\':
                    new_grid[3 * i][3 * j] = 1
                    new_grid[3 * i + 1][3 * j + 1] = 1
                    new_grid[3 * i + 2][3 * j + 2] = 1·
        def dfs(i, j):
            if 0 <= i <3 * m and 0 <= j <3 * n and new_grid[i][j] == 0:
                new_grid[i][j] = 1
                dfs(i + 1, j)
                dfs(i-1, j)
                dfs(i, j + 1)
                dfs(i, j-1)
        for i in range(3 * m):
            for j in range(3 * n):
                if new_grid[i][j] == 0:
                    ans += 1
                    dfs(i, j)
        return ans

The above is the whole content of this article. If you have any thoughts on this, please leave me a message. I will check the answers one by one when I have time. More algorithm routines can visit my LeetCode problem solution warehouse: https://github.com/azl397985856/leetcode. Currently it has 37K stars.

You can also pay attention to my public account "Like Plus" to take you to the hard bones of algorithm.