मान लीजिए हमारे पास एक n x n मैट्रिक्स है। मैट्रिक्स को एक अच्छी मैट्रिक्स कहा जाता है जहां 1 के बराबर नहीं हर संख्या को उसी पंक्ति में एक संख्या और उसी कॉलम में एक संख्या के योग के रूप में व्यक्त किया जा सकता है। हमें जांचना है कि दी गई मैट्रिक्स अच्छी है या नहीं।
इसलिए, यदि इनपुट इस तरह है:
| 1 | 1 | 2 |
| 2 | 3 | 1 |
| 6 | 4 | 1 |
तो आउटपुट True होगा, क्योंकि निचले बाएं कोने में 6 वैध है क्योंकि इसके ऊपर 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 } }आउटपुट
1
