Binary matrix n x n สลับแถวติดกันได้ หา swaps น้อยที่สุดทำให้ทุกค่าบน main diagonal (i > j) เป็น 0 กลยุทธ์: หา rightmost 1 ของแต่ละแถว (m[i]) แล้ว greedy ย้ายแถวที่ m[i] <= allowed position ไปด้านบน นับ swaps
อัลกอริทึม
- m[i] = จำนวนคอลัมน์จากขวาสุดถึง rightmost 1 ของแถว i (ถ้าไม่มี 1 ให้ m[i]=n)
- สำหรับแต่ละแถวเป้าหมาย i (0-indexed): allowed = n - i - 1
- หาแถว j >= i ที่ m[j] <= allowed ใกล้ที่สุด
- Swap แถว j ขึ้นมาตำแหน่ง i (ใช้ swaps = j - i) shift แถวระหว่างลงมา
- ถ้าไม่เจอ: return -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)) # Output: 2
อินพุต/เอาต์พุต
Input: [[0,1,0],[0,1,1],[1,0,0]] Output: 2
