home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Flipped Matrix Prequel in C++: หาจำนวน 1 สูงสุดหลัง Flip Row และ Column

กำหนด binary matrix ต้องหาจำนวน 1 สูงสุดที่ได้หากทำการ flip (0↔1) แถวหนึ่งและคอลัมน์หนึ่ง (flip ทั้งคู่)

ตัวอย่าง: 

1 0 1
0 1 0
1 0 0
→ Output: 8

วิธีแก้ปัญหา

  1. นับจำนวน 1 ในแต่ละแถว (row[i]) และแต่ละคอลัมน์ (col[j]) รวมทั้งหมด (total)
  2. ลอง flip ที่แต่ละตำแหน่ง (i,j) คำนวณจำนวน 1 ใหม่: 
    cand = total - row[i] - col[j] + (m - row[i]) + (n - col[j])
  if matrix[i][j] == 1: cand += 2
  else: cand -= 2
  3. หาค่า max(cand)

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<int> row(n), col(m);
        int total = 0;
        for(int i=0;i

Input

{{1,0,1},{0,1,0},{1,0,0}}

Output

8