Mã C ++ để kiểm tra ma trận đã cho có tốt hay không

Giả sử chúng ta có một ma trận n x n. Ma trận được cho là một ma trận tốt trong đó mọi số không bằng 1 có thể được biểu diễn dưới dạng tổng của một số trong cùng một hàng và một số trong cùng một cột. Chúng ta phải kiểm tra xem ma trận đã cho có tốt hay không.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True, bởi vì số 6 ở góc dưới cùng bên trái là hợp lệ vì khi tổng của 2 ở trên nó và 4 ở bên phải. Điều tương tự cho mọi số không bằng 1 trong ma trận này.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n := size of M
for initialize i := 0, when i < n, update (increase i by 1), do:
   for initialize j := 0, when j < n, update (increase j by 1), do:
      ok := 0
   if M[i, j] is not equal to 1, then:
      c := M[i, j]
   for initialize h := 0, when h < n, update (increase h by 1), do:
      for initialize k := 0, when k < n, update (increase k by 1), do:
         if c is same as M[i, h] + M[k, j], then:
            ok := 1
   if ok is same as 0 and M[i, j] is not equal to 1, then:
      return false
return true

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<vector<int>> M){
   int n = M.size();
   int c;
   bool ok;
   for (int i = 0; i < n; i++){
      for (int j = 0; j < n; j++){
         ok = 0;
         if (M[i][j] != 1)
            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 = 1;
         }
         if (ok == 0 && 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;
}

Đầu vào

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

Đầu ra

1