โปรแกรมนับจำนวนเมทริกซ์ย่อยสี่เหลี่ยมในเมทริกซ์ไบนารีที่กำหนดใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี 2 มิติ เราต้องหาจำนวนทั้งหมดของเมทริกซ์ย่อยในเมทริกซ์ โดยที่องค์ประกอบทั้งหมดคือ 1

ดังนั้นหากอินพุตเป็นแบบ

0	1	1
0	1	1

จากนั้นผลลัพธ์จะเป็น 5 เนื่องจากมีสี่เหลี่ยมจัตุรัสหนึ่ง (2 × 2) และสี่เหลี่ยมจัตุรัส (1 × 1) สี่ช่อง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

ถ้าเสื่อว่างก็
- คืน 0
ค :=0
สำหรับ i ในช่วง 0 ถึงจำนวนแถวของ mat ทำ
- สำหรับ j ในช่วง 0 ถึงจำนวนคอลัมน์ของ mat ให้ทำ
  - ถ้า mat[i, j] คือ 1 แล้ว
    - ถ้าฉันเป็น 0 หรือ j เป็น 0 แล้ว
      - c :=c + 1
    - มิฉะนั้น
      - temp =(ขั้นต่ำของ (mat[i-1, j-1], mat[i, j-1] และ mat[i-1, j]) + mat[i, j]
      - c :=c + อุณหภูมิ
      - mat[i, j] :=อุณหภูมิ
คืนค

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(mat):
   if mat == []:
      return 0
   c = 0

   for i in range(len(mat)):
      for j in range(len(mat[0])):
         if mat[i][j] == 1:
            if i == 0 or j == 0:
               c += 1
            else:
               temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
               c += temp
               mat[i][j] = temp
   return c

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

อินพุต

[[2, 6],[3, 4],[4, 7],[5, 5]]