Chương trình tìm số đảo, từ nơi chúng ta không thể rời khỏi bằng Python

Giả sử chúng ta có một ma trận nhị phân. Ở đây 1 đại diện cho đất và 0 đại diện cho nước. Từ bất kỳ vùng đất nào, chúng ta có thể di chuyển lên, xuống, sang trái hoặc sang phải nhưng không được theo đường chéo sang ô đất khác hoặc đi ra khỏi ma trận. Chúng ta phải tìm số ô đất mà từ đó chúng ta không thể đi ra khỏi ma trận.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 4, vì Có 4 ô đất ở giữa mà từ đó chúng ta không thể rời khỏi ma trận.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• q:=danh sách các cặp (i, j) cho mỗi hàng i và cột khi ma trận [i, j] là vùng đất i và j là các chỉ số đường viền
• idx:=0
• đối với mỗi cặp (x, y) trong q, thực hiện
  • ma trận [x, y]:=0
• while idx
• x, y:=q [idx]
• cho mỗi (dx, dy) trong [(-1, 0), (0, -1), (0, 1), (1, 0)], thực hiện
  • nx:=x + dx
  • ny:=y + dy
  • nếu 0 <=nx
  • ma trận [nx, ny]:=0
  • insert (nx, ny) vào cuối q

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def solve(matrix):
   q = [(i, j) for i in range(len(matrix)) for j in range(len(matrix[i])) if matrix[i][j] and (i == 0 or i == len(matrix) - 1 or j == 0 or j == len(matrix[i]) - 1)]
   idx = 0
   for x, y in q:
      matrix[x][y] = 0
   while idx < len(q):
      x, y = q[idx]
      for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
         nx, ny = x + dx, y + dy
         if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
            matrix[nx][ny] = 0
            q.append((nx, ny))
      idx += 1
   return sum(sum(row) for row in matrix)

matrix = [
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]
print(solve(matrix))

Đầu vào

[
[0, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1]
]

Đầu ra

4