एक बाइनरी मैट्रिक्स दी गई है, हमें प्रत्येक सेल से निकटतम सेल तक की न्यूनतम दूरी ज्ञात करनी है जिसमें 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
