주어진 행렬이 좋은지 여부를 확인하는 C++ 코드

<시간/>

하나의 n x n 행렬이 있다고 가정합니다. 행렬은 1이 아닌 모든 숫자가 같은 행의 숫자와 같은 열의 숫자의 합으로 표현될 수 있는 좋은 행렬이라고 합니다. 주어진 행렬이 좋은지 아닌지를 확인해야 합니다.

따라서 입력이 다음과 같으면

1	1	2
2	3	1
6	4	1

왼쪽 하단 모서리의 6이 유효하기 때문에 출력은 True가 됩니다. 왜냐하면 위의 2와 오른쪽의 4의 합이 유효하기 때문입니다. 이 행렬에서 1이 아닌 모든 숫자에 대해서도 마찬가지입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

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

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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;
}

입력

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