मान लीजिए हमारे पास एक 2D बाइनरी मैट्रिक्स है जहां 1 एक कम्युनिकेशन टावर को दर्शाता है, और 0 एक खाली सेल को दर्शाता है। टावर निम्न तरीकों से संवाद कर सकते हैं:
- यदि टावर A और टावर B एक ही पंक्ति या कॉलम पर हैं, तो वे एक-दूसरे से संवाद कर सकते हैं।
- यदि टावर A, टावर B से बात कर सकता है और B, C से बात कर सकता है, तो A, C से बात कर सकता है (संक्रामक गुण)।
हमें टावर समूहों की कुल संख्या ज्ञात करनी है (एक समूह उन टावर्स की सूची है जो एक-दूसरे से बात कर सकते हैं)।
उदाहरण के लिए, इनपुट मैट्रिक्स:
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 1 |
आउटपुट 1 होगा क्योंकि सभी टावर एक-दूसरे से जुड़े हुए हैं।
समाधान दृष्टिकोण (DFS)
dfs()फ़ंक्शन परिभाषित करें जो मैट्रिक्स, i, j, n, m लेता है।matrix[i][j] := 2(विज़िटेड मार्क करें)।- उसी कॉलम में सभी पंक्तियों k के लिए:
p = (i+k)%n, q = j; यदिmatrix[p][q] == 1तो DFS कॉल करें। - उसी पंक्ति में सभी कॉलम k के लिए:
p = i, q = (j+k)%m; यदिmatrix[p][q] == 1तो DFS कॉल करें। - मेन मेथड में: सभी सेल्स को पार करें, यदि 1 मिले तो
ans++करें और DFS कॉल करें।
उदाहरण (C++ कोड)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void dfs(vector<vector<int>>& matrix, int i, int j, int& n, int& m) {
matrix[i][j] = 2;
for (int k = 1; k < n; k++) {
int p = (i + k) % n, q = j;
if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
}
for (int k = 1; k < m; k++) {
int p = i, q = (j + k) % m;
if (matrix[p][q] == 1) dfs(matrix, p, q, n, m);
}
}
int solve(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
ans++;
dfs(matrix, i, j, n, m);
}
}
}
return ans;
}
};
int main() {
vector<vector<int>> v = {{1,1,0}, {0,0,1}, {1,0,1}};
cout << (new Solution())->solve(v);
return 0;
} इनपुट
{{1,1,0}, {0,0,1}, {1,0,1}} आउटपुट
1