एक बाइनरी मैट्रिक्स को देखते हुए, हमें प्रत्येक सेल से निकटतम सेल तक न्यूनतम दूरी खोजने की जरूरत है जिसमें 1.
आइए एक उदाहरण देखें।
इनपुट
0 0 1 1 1 0 0 0 0
आउटपुट
1 1 0 0 0 1 1 1 2
न्यूनतम दूरी वह है जो वर्तमान सेल पंक्ति - 1 सेल पंक्ति + वर्तमान सेल कॉलम - 1 सेल कॉलम से न्यूनतम हो।
एल्गोरिदम
-
वांछित आकार के मैट्रिक्स को प्रारंभ करें।
-
दूरी को स्टोर करने के लिए समान आकार का दूसरा मैट्रिक्स प्रारंभ करें।
-
संपूर्ण मैट्रिक्स पर पुनरावृति करें
.-
यदि वर्तमान सेल मान 1 है, तो दूरी को 0 पर सेट करें क्योंकि 1 से 1 की दूरी 0 है
-
यदि वर्तमान सेल मान 0
. है-
संपूर्ण मैट्रिक्स पर पुन:पुनरावृति करें
-
यदि सेल 1 है, तो वर्तमान सेल से दूरी की गणना करें।
-
न्यूनतम दूरी अपडेट करें।
।
-
-
-
दूरी मैट्रिक्स प्रिंट करें।
कार्यान्वयन
C++ में उपरोक्त एल्गोरिथम का कार्यान्वयन निम्नलिखित है
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> findNearest1Distance(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (rows == 0) {
return matrix;
}
int cols = matrix[0].size();
vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
distance[i][j] = 0;
}else if (matrix[i][j] == 0) {
for (int k = 0; k < rows; k++) {
for (int l = 0; l < cols; l++) {
if (matrix[k][l] == 1) {
distance[i][j] = min(distance[i][j], abs(k - i) + abs(l - j));
}
}
}
}
}
}
return distance;
}
int main() {
vector<vector<int>> matrix{
{0, 0, 1},
{1, 1, 0},
{0, 0, 0}
};
vector<vector<int>> result = findNearest1Distance(matrix);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
return 0;
} आउटपुट
यदि आप उपरोक्त कोड चलाते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
1 1 0 0 0 1 1 1 2