ค้นหาสี่เหลี่ยมทั้งหมดที่มี 0 ใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติแบบไบนารี ตอนนี้เราต้องหาจุดเริ่มต้นและจุดสิ้นสุดของสี่เหลี่ยมทั้งหมดที่มี 0 เราต้องจำไว้ว่าสี่เหลี่ยมถูกแยกออกจากกันและไม่สัมผัสกัน แต่สามารถสัมผัสขอบเขตอาร์เรย์ได้ สี่เหลี่ยมที่มีองค์ประกอบเดียวก็เป็นไปได้เช่นกัน

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

จากนั้นผลลัพธ์จะเป็น [[0, 1, 0, 1], [0, 5, 0, 5], [1, 2, 1, 2], [2, 3, 2, 4], [3, 1 , 5, 1], [3, 4, 6, 5], [5, 3, 6, 5], [7, 1, 7, 1], [7, 5, 7, 5]]

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

• กำหนดฟังก์ชัน find_rect() นี่จะใช้เวลา i,j,a,output,index
• x :=จำนวนแถว
• y :=จำนวนคอล
• flag_col :=0
• flag_row :=0
• สำหรับ m ในช่วง i ถึง x ทำ
  • ถ้า a[m, j] เหมือนกับ 1 แล้ว
    • flag_row :=1
    • แตก
  • ถ้า a[m, j] เท่ากับ 5 แล้ว
    • ไม่ทำอะไรเลย
  • สำหรับ n ในช่วง j ถึง y ทำ
    • ถ้า a[m, n] เหมือนกับ 1 แล้ว
      • flag_col :=1
      • แตก
    • a[m, n] :=5
  • ถ้า flag_row เหมือนกับ 1 แล้ว
    • แทรก m-1 ที่ส่วนท้ายของเอาต์พุต[index]
  • มิฉะนั้น
    • แทรก m ที่ส่วนท้ายของเอาต์พุต[index]
  • ถ้า flag_col เหมือนกับ 1 แล้ว
    • แทรก n-1 ที่ส่วนท้ายของเอาต์พุต[index]
  • มิฉะนั้น
    • ใส่ n ที่ส่วนท้ายของเอาต์พุต[index]
• จากวิธีหลัก ให้ทำดังต่อไปนี้ −
• n :=ขนาดของ a
• op :=รายการใหม่
• idx :=-1
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • สำหรับ j ในช่วง 0 ถึงขนาด a[0] ทำ
    • ถ้า a[i, j] เหมือนกับ 0 แล้ว
      • แทรก [i,j] ลงใน op
      • idx :=idx + 1
      • find_rect(i, j, a, op, idx)
• ตัวเลือกการแสดงผล

โค้ดตัวอย่าง

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

def find_rect(i,j,a,output,index):x =len(a) y =len(a[0]) flag_col =0 flag_row =0 สำหรับ m ในช่วง (i,x):ถ้า [m][j] ==1:flag_row =1 break if a[m][j] ==5:ส่งผ่านสำหรับ n ในช่วง (j, y):if a[m][n] ==1:flag_col =1 แบ่ง a[m][n] =5 ถ้า flag_row ==1:output[index].append( m-1) อื่น:output[index].append(m) if flag_col ==1:output[index] .append(n-1) อื่น:output[index].append(n)def get_coord(a):n =len(a) op =[] idx =-1 for i in range(0,n):for j ในช่วง(0, len(a[0])):ถ้า a[i][j] ==0:op.append([i, j]) idx =idx + 1 find_rect(i, j, a, op , idx) พิมพ์ (op) การทดสอบ =[[1, 0, 1, 1, 1, 0, 1], [1, 1, 0, 1, 1, 1, 1], [1, 1, 1, 0 , 0, 1, 1], [1, 0, 1, 1, 0, 0, 1], [1, 0, 1, 1, 0, 1, 1], [1, 0, 1, 0, 0 , 0, 0], [1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1]]get_coord(ทดสอบ) 
อินพุต
 <ก่อนหน้า>[[1, 0, 1, 1, 1, 0, 1],[1, 1, 0, 1, 1, 1, 1],[1, 1, 1, 0, 0, 1, 1 ],[1, 0, 1, 1, 0, 0, 1],[1, 0, 1, 1, 0, 1, 1],[1, 0, 1, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1],[1, 0, 1, 1, 1, 0, 1]]

ผลลัพธ์

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