Số ô lẻ trong ma trận sau khi tăng hàng/cột C++

Cho ma trận n×m khởi tạo 0. Mảng indices[i] = [ri, ci]. Mỗi cặp tăng tất cả ô hàng ri và cột ci lên 1. Đếm số ô có giá trị lẻ sau tất cả thao tác.

Ví dụ

n=2, m=3, indices = [[0,1],[1,1]]

Ma trận ban đầu: 0 0 0 / 0 0 0

Sau [0,1]: hàng 0 +1, cột 1 +1 → 1 2 1 / 0 1 0

Sau [1,1]: hàng 1 +1, cột 1 +1 → 1 3 1 / 1 2 1

Ô lẻ: 6 ô (tất cả)

Thuật toán mô phỏng

Tạo ma trận, duyệt indices, tăng hàng và cột tương ứng, cuối cùng đếm ô lẻ (value & 1).

Chương trình mẫu

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

class Solution {
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<vector<int>> mat(n, vector<int>(m, 0));
        
        for (auto& idx : indices) {
            int r = idx[0], c = idx[1];
            for (int j = 0; j < m; j++) mat[r][j]++;
            for (int i = 0; i < n; i++) mat[i][c]++;
        }
        
        int odd = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                odd += (mat[i][j] & 1); // kiểm tra bit thấp nhất
        return odd;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> c = {{0,1}, {1,1}};
    cout << ob.oddCells(2, 3, c);
    return 0;
}

Kết quả

6

Tối ưu O(n+m+k): Chỉ cần đếm số lần mỗi hàng/cột bị tăng.

int oddCells(int n, int m, vector<vector<int>>& indices) {
    vector<int> row(n, 0), col(m, 0);
    for (auto& idx : indices) {
        row[idx[0]]++;
        col[idx[1]]++;
    }
    int odd = 0;
    for (int r : row)
        for (int c : col)
            odd += ((r + c) & 1);
    return odd;
}

Ô (i,j) bị tăng row[i] + col[j] lần. Lẻ khi tổng này lẻ.