Chương trình tìm khoảng cách cầu ngắn nhất giữa các đảo bằng Python

Giả sử chúng ta có một ma trận nhị phân, trong đó 0 đại diện cho nước và 1 đại diện cho đất. Đảo là một nhóm kết nối các 1 theo 4 hướng. Các đảo được bao quanh bởi các số 0 (nước) hoặc bởi các cạnh. Chúng ta phải tìm chiều dài của cây cầu ngắn nhất nối hai hòn đảo.

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

0	0	1
1	0	1
1	0	0

thì đầu ra sẽ là 1. Điều này sẽ kết nối (1,0) với (1,2) điểm.

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

row:=số hàng của ma trận
col:=số cột của ma trận
Định nghĩa một hàm dfs (). Điều này sẽ mất i, j, s
nếu (i, j) bằng s, thì
- trở lại
nếu mat [i, j] giống 0 thì
- trở lại
chèn (i, j) vào s
nếu tôi - 1> =0, thì
- dfs (i - 1, j, s)
nếu tôi + 1
- dfs (i + 1, j, s)
nếu j - 1> =0, thì
- dfs (i, j - 1, s)
nếu j + 1
- dfs (i, j + 1, s)
Từ phương thức chính, hãy làm như sau -
đã thấy:=một tập hợp mới
đối với tôi trong phạm vi từ 0 đến hàng, hãy thực hiện
- nếu kích thước của saw> 0, thì
  - đi ra từ vòng lặp
- đối với j trong phạm vi 0 đến col, do
  - nếu mat [i, j] giống 1 thì
    - dfs (i, j, saw)
    - đi ra từ vòng lặp
q:=một hàng đợi kết thúc kép
đối với mỗi vùng đất đã thấy, hãy thực hiện
- (i, j):=land
- nếu i - 1> =0 và mat [i - 1, j] giống 0 thì
  - insert (i - 1, j, 1) vào cuối q
- nếu i + 1
  - insert (i + 1, j, 1) vào cuối q
- nếu j - 1> =0 và mat [i, j - 1] giống 0 thì
  - insert (i, j - 1, 1) vào cuối q
- nếu j + 1
  - insert (i, j + 1, 1) vào cuối q
trong khi kích thước của q> 0, thực hiện
- (i, j, dist):=mục bên trái của q và xóa mục bên trái của q
- nếu (i, j) được nhìn thấy, thì
  - chuyển sang lần lặp tiếp theo
- đánh dấu (i, j) như đã thấy
- nếu mat [i, j] giống 1 thì
  - trả về dist - 1
- nếu tôi - 1> =0, thì
  - insert (i - 1, j, dist + 1) vào cuối q
- nếu i + 1
  - insert (i + 1, j, dist + 1) vào cuối q
- nếu j - 1> =0, thì
  - insert (i, j - 1, dist + 1) vào cuối q
- nếu j + 1
  - chèn (i, j + 1, dist + 1) 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 -

import collections
class Solution:
   def solve(self, mat):
      row = len(mat)
      col = len(mat[0])
      def dfs(i, j, s):
         if (i, j) in s:
            return
         if mat[i][j] == 0:
            return
         s.add((i, j))
         if i - 1 >= 0:
            dfs(i - 1, j, s)
         if i + 1 < row:
            dfs(i + 1, j, s)
         if j - 1 >= 0:
            dfs(i, j - 1, s)
         if j + 1 < col:
            dfs(i, j + 1, s)
      seen = set()
      for i in range(row):
         if len(seen) > 0:
            break
         for j in range(col):
            if mat[i][j] == 1:
               dfs(i, j, seen)
               break
      q = collections.deque()
      for land in seen:
         i, j = land
         if i - 1 >= 0 and mat[i - 1][j] == 0:
            q.append((i - 1, j, 1))
         if i + 1 < row and mat[i + 1][j] == 0:
            q.append((i + 1, j, 1))
         if j - 1 >= 0 and mat[i][j - 1] == 0:
            q.append((i, j - 1, 1))
         if j + 1 < col and mat[i][j + 1] == 0:
            q.append((i, j + 1, 1))
      while len(q) > 0:
         i, j, dist = q.popleft()
         if (i, j) in seen:
            continue
         seen.add((i, j))
         if mat[i][j] == 1:
            return dist - 1
         if i - 1 >= 0:
            q.append((i - 1, j, dist + 1))
         if i + 1 < row:
            q.append((i + 1, j, dist + 1))
         if j - 1 >= 0:
            q.append((i, j - 1, dist + 1))
         if j + 1 < col:
            q.append((i, j + 1, dist + 1))
ob = Solution()
matrix = [
   [0, 0, 1],
   [1, 0, 1],
   [1, 0, 0],
]
print(ob.solve(matrix))

Đầu vào

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

Chương trình tìm khoảng cách cầu ngắn nhất giữa các đảo bằng Python

Ví dụ

Đầu vào

Đầu ra