C++: Kiểm tra ma trận "tốt" (good matrix)

Bài toán: Ma trận n×n gọi là "tốt" nếu mọi phần tử ≠ 1 đều biểu diễn được như tổng của một phần tử cùng hàng và một phần tử cùng cột. Kiểm tra ma trận có tốt không.

Thuật toán

Duyệt mọi ô (i,j). Nếu M[i][j] != 1, kiểm tra tồn tại h,k sao cho M[i][h] + M[k][j] == M[i][j]. O(n⁴) naïve, đủ cho n nhỏ.

Code C++

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

bool solve(vector<vector<int>> M) {
    int n = M.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (M[i][j] == 1) continue;
            int target = M[i][j];
            bool ok = false;
            for (int h = 0; h < n && !ok; h++)
                for (int k = 0; k < n; k++)
                    if (M[i][h] + M[k][j] == target) { ok = true; break; }
            if (!ok) return false;
        }
    }
    return true;
}

int main() {
    vector<vector<int>> M = {{1,1,2}, {2,3,1}, {6,4,1}};
    cout << solve(M) << endl; // 1 (true)
    return 0;
}

Kết quả

1

Ví dụ: 6 = 2 (cùng cột) + 4 (cùng hàng). Tất cả ô ≠ 1 đều thỏa mãn.