โปรแกรมหาผลรวมสูงสุดจากการพลิกบิตแถวในเมทริกซ์ไบนารี Python

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

ตัวอย่าง: อินพุตคือ

ผลลัพธ์คือ 11 เพราะหากพลิกทั้งสองแถว จะได้ 101 (5) และ 110 (6) ผลรวม = 11

ขั้นตอนการแก้ปัญหา

1. วนลูปแต่ละแถว r ในเมทริกซ์:
   • หาก r[0] == 0 ให้พลิกบิตทั้งแถว (r[i] = -r[i] + 1)
2. วนลูปคอลัมน์ j ตั้งแต่ 1 ถึงคอลัมน์สุดท้าย:
   • นับ cnt = จำนวน 1 ลบ จำนวน 0 ในคอลัมน์นั้น
   • หาก cnt < 0 ให้พลิกบิตทั้งคอลัมน์นั้น
3. คำนวณผลรวม: แปลงแต่ละแถวเป็นเลขฐานสิบและบวกกัน

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

class Solution:
    def solve(self, matrix):
        for r in matrix:
            if r[0] == 0:
                for i in range(len(r)):
                    r[i] = -r[i] + 1
        
        for j in range(1, len(matrix[0])):
            cnt = 0
            for i in range(len(matrix)):
                cnt += 1 if matrix[i][j] else -1
            if cnt < 0:
                for i in range(len(matrix)):
                    matrix[i][j] = -matrix[i][j] + 1
        
        ans = 0
        for r in matrix:
            a = 0
            for v in r:
                a = 2 * a + v
            ans += a
        return ans

ob = Solution()
matrix = [[0, 1, 0], [0, 0, 1]]
print(ob.solve(matrix))  # Output: 11

อินพุต

[[0, 1, 0], [0, 0, 1]]

เอาต์พุต

11