โปรแกรมหาค่าสูงสุดของ k ซึ่งเราสามารถรักษาระยะห่างที่ปลอดภัยใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี ในที่นี้ 0 หมายถึงเซลล์ว่าง และ 1 หมายถึงเซลล์ที่มีบุคคล ระยะห่างระหว่างสองเซลล์คือค่าสูงสุดระหว่างความแตกต่างในพิกัด x และความแตกต่างในพิกัด y ตอนนี้เมทริกซ์ถือว่าปลอดภัยโดยมีตัวประกอบ k หากมีสี่เหลี่ยมว่างที่ระยะห่างจากเซลล์ถึงแต่ละคนในเมทริกซ์ และแต่ละด้านของเมทริกซ์มีค่ามากกว่าหรือเท่ากับ k เราต้องหาค่าสูงสุดของแฟคเตอร์ k ให้ได้ เพื่อความปลอดภัย

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

ผลลัพธ์จะเป็น 1 เช่นเดียวกับในเซลล์ตรงกลาง ระยะห่างจากเซลล์ถึงแต่ละคนในตารางอย่างน้อย 1

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

• N :=ขนาด A

• M :=ขนาด A[0]

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

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

    • A[i, j] :=A[i, j] XOR 1

• ตอบ :=0

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

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

    • ถ้า i และ j ไม่ใช่ศูนย์ และ A[i, j] เป็น 1 แล้ว

      • A[i, j] :=1 + ค่าต่ำสุดของ A[i - 1, j], A[i, j - 1] และ A[i - 1, j - 1]

      • ans =สูงสุดของ A[i, j] และ ans

• ผลตอบแทน (ans + 1) / 2

ตัวอย่าง

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

คลาส Solution:def แก้ (ตัวเอง, A):N =len(A) M =len(A[0]) สำหรับ i ในช่วง (N):สำหรับ j ในช่วง (M):A[i][ j] ^=1 ans =0 สำหรับฉันในช่วง (N):สำหรับ j ในช่วง (M):ถ้า i และ j และ A[i][j]:A[i][j] =1 + นาที (A [i - 1][j], A[i][j - 1], A[i - 1][j - 1]) ans =max(A[i][j], ans) ผลตอบแทน (ans + 1 ) // 2ob =สารละลาย()เมทริกซ์ =[ [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0],]พิมพ์(ob.solve(เมทริกซ์))

อินพุต

ผลลัพธ์

1