Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình đếm số đảo chồng lên nhau trong hai bản đồ bằng Python

Giả sử chúng ta có hai ma trận nhị phân mat1 và mat2. Ở đây 1 đại diện cho đất và 0 đại diện cho nước, nếu có một nhóm 1 (đất) bao quanh bởi nước được gọi là đảo. Chúng ta phải tìm số lượng các hòn đảo tồn tại trong cả mat1 và mat2 ở cùng một tọa độ chính xác.

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

1 0 1
1 0 0
1 0 0

Và mat2 =

1 0 1
1 0 0
1 0 1

thì đầu ra sẽ là 2, vì các đảo chồng lên nhau,

1 0 1
1 0 0
1 0 1

vì vậy có hai hòn đảo chồng lên nhau.

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

  • r:=số hàng của mat1
  • c:=số cột của mat1
  • last_row:=r - 1
  • last_col:=c - 1
  • Xác định một dấu chức năng (). Điều này sẽ mất tôi, j
  • mat1 [i, j]:=0
  • mat2 [i, j]:=0
  • nếu tôi khác 0 và (mat1 [i - 1, j] hoặc mat2 [i - 1, j] bất kỳ cái nào khác 0), thì
    • mark (i - 1, j)
  • nếu j khác 0 và (mat1 [i, j - 1] hoặc mat2 [i, j - 1] bất kỳ cái nào khác 0) thì
    • mark (i, j - 1)
  • nếu j
  • mark (i, j + 1)
  • nếu tôi
  • mark (i + 1, j)
  • Từ phương pháp chính, hãy thực hiện như sau -
  • đối với tôi trong phạm vi từ 0 đến r - 1, thực hiện
    • đối với j trong phạm vi từ 0 đến c - 1, thực hiện
      • nếu mat1 [i, j] không giống với mat2 [i, j], thì
        • mark (i, j)
  • đảo:=0
  • đối với tôi trong phạm vi từ 0 đến r - 1, thực hiện
    • đối với j trong phạm vi từ 0 đến c - 1, thực hiện
      • nếu mat1 [i, j] khác 0, thì
        • đảo:=đảo + 1
        • đánh dấu (i, j)
  • đảo trở lại

    • Ví dụ

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

    def solve(mat1, mat2):
   r = len(mat1)
   c = len(mat1[0])
   last_row = r - 1
   last_col = c - 1

   def mark(i, j):
      mat1[i][j] = mat2[i][j] = 0
      if i and (mat1[i - 1][j] or mat2[i - 1][j]):
         mark(i - 1, j)
      if j and (mat1[i][j - 1] or mat2[i][j - 1]):
         mark(i, j - 1)
      if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
         mark(i, j + 1)
      if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
         mark(i + 1, j)

   for i in range(r):
      for j in range(c):
         if mat1[i][j] != mat2[i][j]:
            mark(i, j)

   islands = 0
   for i in range(r):
      for j in range(c):
         if mat1[i][j]:
            islands += 1
            mark(i, j)
   return islands

mat1 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
mat2 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
print(solve(mat1, mat2))

    Đầu vào 

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

    Đầu ra 

    2