C++: Tìm điểm ô thắng trên bàn cờ vuông

Bài toán: Bàn cờ n×n. Ô (i,j) là "thắng" nếu tổng cột j > tổng hàng i. Đếm số ô thắng.

Thuật toán

1. Tính trước tổng mỗi hàng rowSum[i] và tổng mỗi cột colSum[j] (O(n²)).
2. Duyệt mọi ô, đếm nếu colSum[j] > rowSum[i].
3. Tổng O(n²).

Code C++

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

int solve(vector<vector<int>> M) {
    int n = M.size();
    vector<int> rowSum(n, 0), colSum(n, 0);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            rowSum[i] += M[i][j];
            colSum[j] += M[i][j];
        }

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (colSum[j] > rowSum[i]) cnt++;

    return cnt;
}

int main() {
    vector<vector<int>> matrix = {
        {5, 7, 8, 4},
        {9, 5, 3, 2},
        {1, 6, 6, 4},
        {9, 5, 7, 3}
    };
    cout << solve(matrix) << endl; // 6
    return 0;
}

Kết quả

6

Các ô thắng được tô màu trong ví dụ gốc.