สมมติว่าเรามีเมทริกซ์ไบนารี n x n เราสามารถดำเนินการกับมันได้เช่นเดียวกับในขั้นตอนเดียวเราเลือกแถวที่อยู่ติดกันสองแถวและสลับกัน เราต้องนับจำนวน swap ขั้นต่ำที่จำเป็น เพื่อให้โหนดทั้งหมดที่อยู่เหนือเส้นทแยงมุมหลักของเมทริกซ์เป็น 0 หากไม่มีวิธีแก้ปัญหาดังกล่าว ให้คืนค่า -1
ดังนั้นหากอินพุตเป็นแบบ
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
ผลลัพธ์จะเป็น 2 เพราะ −
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
n :=จำนวนแถวของเมทริกซ์
-
m :=สร้างอาร์เรย์ขนาด n และเติมด้วย n
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
สำหรับ j ในช่วง n-1 ถึง 0, ลดลง 1 ทำ
-
ถ้า matrix[i, j] เท่ากับ 1 แล้ว
-
m[i] :=n-j-1
-
ออกจากวง
-
-
-
-
t :=0, ans :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
t :=t + 1
-
ธง :=เท็จ
-
สำหรับ j ในช่วง i ถึง n - 1 ทำ
-
ถ้า m[j]>=n-t แล้ว
-
ans :=ans + j-i
-
ธง :=จริง
-
ออกจากวง
-
-
-
หากแฟล็กเป็นเท็จ
-
กลับ -1
-
-
อัปเดต m[จากดัชนี i+1 เป็น j] โดย m[จากดัชนี i เป็น j-1]
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(matrix): n = len(matrix) m = [n] * n for i in range(n): for j in range(n-1,-1,-1): if matrix[i][j] == 1: m[i] = n-j-1 break t,ans = 0,0 for i in range(n): t += 1 flag = False for j in range(i,n): if m[j] >= n-t: ans += j-i flag = True break if not flag: return -1 m[i+1:j+1] = m[i:j] return ans matrix = [[0,1,0],[0,1,1],[1,0,0]] print(solve(matrix))
อินพุต
[[0,1,0],[0,1,1],[1,0,0]]
ผลลัพธ์
2
