โค้ด C++ ตรวจสอบเมทริกซ์ดีหรือไม่

โจทย์: เมทริกซ์ n×n เป็น "ดี" ถ้าทุกค่าที่ไม่ใช่ 1 แสดงเป็นผลรวมของค่าในแถวเดียวกันและคอลัมน์เดียวกันได้ ตรวจสอบว่ามีทิศดีหรือไม่

Input: [[1,1,2],[2,3,1],[6,4,1]] → Output: True (6 = 2+4, 2=1+1, 3=2+1, 4=3+1)

ขั้นตอนแก้

for each cell (i,j):
    if M[i][j] != 1:
        ok := false
        c := M[i][j]
        for h := 0 to n-1:
            for k := 0 to n-1:
                if c == M[i][h] + M[k][j]: ok = true
        if not ok: return false
return true

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

#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++) {
            bool ok = false;
            if (M[i][j] != 1) {
                int c = M[i][j];
                for (int h = 0; h < n; h++)
                    for (int k = 0; k < n; k++)
                        if (c == M[i][h] + M[k][j]) ok = true;
            }
            if (!ok && M[i][j] != 1) return false;
        }
    }
    return true;
}
int main() {
    vector<vector<int>> matrix = {{1,1,2},{2,3,1},{6,4,1}};
    cout << solve(matrix) << endl;
}

Input

{{1,1,2},{2,3,1},{6,4,1}}

Output

1