โปรแกรมลบเกาะทั้งหมดที่มีน้ำล้อมรอบใน Python

สมมติว่าเรามีเมทริกซ์ไบนารีโดยที่ 1 แทนดิน และ 0 แทนน้ำ และเกาะคือกลุ่มของ 1 ที่ล้อมรอบด้วย 0 (น้ำ) หรือตามขอบ เราต้องหาเกาะทั้งหมดที่ล้อมรอบด้วยน้ำและแปลงเป็น 0 ดังที่ทราบกันดีว่าเกาะจะแล้วเสร็จล้อมรอบด้วยน้ำหากเพื่อนบ้านทั้งหมด (แนวนอนและแนวตั้งไม่ทแยง) เป็น 0 (เพื่อนบ้านไม่มีขอบ)

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

แล้วผลลัพธ์ที่ได้จะเป็น

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

• row :=จำนวนแถวของ A

• col :=จำนวนคอลัมน์ของ A

• B :=เมทริกซ์ขนาด A และเติมด้วย 0

• เห็นแล้ว :=ชุดใหม่

• สำหรับผมอยู่ในช่วง 0 ถึงแถว ทำ

  • สำหรับ j ในช่วง 0 ถึง col ทำ

    • ถ้า i และ j ไม่อยู่ในช่วงของเมทริกซ์

      • ไปทำซ้ำต่อไป

    • ถ้าเห็น (i, j) แล้ว

      • ไปทำซ้ำต่อไป

    • ถ้า A[i, j] เท่ากับ 0 แล้ว

      • ไปทำซ้ำต่อไป

    • d :=คิวสองสิ้นสุดที่มีองค์ประกอบเดียว (i, j)

    • ในขณะที่ d ไม่ว่างให้ทำ

      • (x, y) :=เหลือองค์ประกอบ d และลบออกจาก d

      • B[x, y] :=1

      • สำหรับเพื่อนบ้านแต่ละคน (x2, y2) ของ (x, y) ทำ

        • ถ้าไม่เห็น (x2, y2) แล้ว

          • แทรก (x2, y2) ที่ส่วนท้ายของ d

          • ทำเครื่องหมาย (x2, y2) ตามที่เห็น

• กลับ B

ตัวอย่าง

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

จากคอลเลกชันนำเข้า dequeclass โซลูชัน:def แก้ปัญหา(ตัวเอง, A):row =len(A) col =len(A[0]) B =[[0 สำหรับ _ ในช่วง (col)] สำหรับ _ ในช่วง row)] seen =set() def nei(i, j):if i + 1 =0 และ A[i - 1][j]:ผลผลิต (i - 1, j) ถ้า j - 1>=0 และ A[i][j - 1]:ผลตอบแทน (i, j - 1) สำหรับฉันในช่วง (แถว):สำหรับ j ในช่วง (col):ถ้าฉันไม่ได้อยู่ใน (0, แถว - 1) และ j ไม่อยู่ใน ( 0, col - 1):ทำต่อถ้า (i, j) เห็น:ทำต่อถ้า A[i][j] ==0:ทำต่อ d =deque([(i, j)]) ในขณะที่ d:x, y =d.popleft() B[x][y] =1 สำหรับ x2, y2 ใน nei(x, y):ถ้า (x2, y2) ไม่เห็น:d.append((x2, y2)) seen.add((x2, y2)) return Bob =Solution()matrix =[ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [ 0, 1, 1, 0], [0, 0, 0, 1],]print(ob.solve(matrix))

อินพุต

ผลลัพธ์