একটি বাইনারি ম্যাট্রিক্স দেওয়া হলে, আমাদের প্রতিটি সেল থেকে নিকটতম কক্ষের ন্যূনতম দূরত্ব খুঁজে বের করতে হবে যাতে 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
