সি++-এ বাইনারি ম্যাট্রিক্সে প্রতিটি সেল থেকে নিকটতম ১-এর দূরত্ব

একটি বাইনারি ম্যাট্রিক্স দেওয়া থাকলে, প্রতিটি সেল থেকে নিকটতম ১-ন 国道 মানহ্যাটান দূরত্ব বের করতে হবে।

উদাহরণ

ইনপুট:

0 0 1
1 1 0
0 0 0

আউটপুট:

1 1 0
0 0 1
1 1 2

অ্যালগরিদম (BFS - আরও দক্ষ)

• সকল ১-এর অবস্থান কিউতে রাখুন, দূরত্ব ০।
• BFS চালিয়ে প্রতিটি ০-এর জন্য নিকটতম ১-এর দূরত্ব বের করুন।
• সময় জটিলতা: O(rows × cols)।

সি++ ইমপ্লিমেন্টেশন (সহজ ব্রুট ফোর্স)

#include <bits/stdc++.h>
using namespace std;

vector> findNearest1Distance(vector>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return matrix;
    int cols = matrix[0].size();
    vector> dist(rows, vector(cols, INT_MAX));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 1) dist[i][j] = 0;
            else {
                for (int k = 0; k < rows; k++) {
                    for (int l = 0; l < cols; l++) {
                        if (matrix[k][l] == 1) {
                            dist[i][j] = min(dist[i][j], abs(k-i) + abs(l-j));
                        }
                    }
                }
            }
        }
    }
    return dist;
}

int main() {
    vector> matrix = {{0,0,1}, {1,1,0}, {0,0,0}};
    auto result = findNearest1Distance(matrix);
    for (auto& row : result) {
        for (int val : row) cout << val << " ";
        cout << endl;
    }
    return 0;
}

আউটপুট

1 1 0
0 0 1
1 1 2