C++-এ সব বিল্ডিং থেকে ন্যূনতম দূরত্বে ঘর বানানো (Shortest Distance from All Buildings)

ধরি আমরা একটি খালি জমিতে ঘর বানাতে চাই যেটি সব বিল্ডিং থেকে সবচেয়ে কম দূরত্বে থাকে। আমরা চার দিকেই (উপরে, নিচে, বামে, ডানে) চলতে পারি। আমাদের একটি 2D গ্রিড আছে যার মান 0, 1 বা 2:

0 = খালি জমি (এখান থেকে বাধা ছাড়া যাওয়া যায়)
1 = বিল্ডিং (এখান থেকে যাওয়া যায় না)
2 = বাধা (এখান থেকে যাওয়া যায় না)

উদাহরণস্বরূপ, গ্রিড:

1	2	1
0	0	0
0	1	0

আউটপুট হবে 7 কারণ তিনটি বিল্ডিং আছে (0,0), (0,4), (2,2) এবং একটি বাধা (0,2)। পয়েন্ট (1,2) আদর্শ খালি জমি, কারণ মোট দূরত্ব 3+3+1=7 ন্যূনতম।

সমাধানের ধাপসমূহ

ret := INF
n := গ্রিডের সারি, m := কলাম
numberOfOnes := 0
দুটি 2D অ্যারে dist এবং reach আকার n x m
প্রতিটি সেল (i,j) জন্য যদি grid[i][j] == 1:
- numberOfOnes++
- একটি কিউ q, {i,j} পুশ
- একটি সেট visited
- lvl = 1 থেকে q খালি না হওয়া পর্যন্ত:
  - sz := q.size()
  - sz বার:
    - curr := q.front(); q.pop()
    - x,y := curr
    - k = 0 থেকে 3:
      - nx := x + dir[k][0], ny := y + dir[k][1]
      - যদি নেট বাহিরে বা grid[nx][ny] != 0: continue
      - visited-এ {nx,ny} ইনসার্ট
      - dist[nx][ny] += lvl
      - reach[nx][ny]++
      - q-তে {nx,ny} পুশ
সব সেল (i,j) জন্য যদি grid[i][j]==0 এবং reach[i][j]==numberOfOnes: ret = min(ret, dist[i][j])
ফেরত: (ret == INF ? -1 : ret)

প্রোগ্রাম উদাহরণ

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

class Solution {
public:
    int shortestDistance(vector>& grid) {
        int ret = INT_MAX;
        int n = grid.size();
        int m = grid[0].size();
        int numberOfOnes = 0;
        vector> dist(n, vector(m));
        vector> reach(n, vector(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    numberOfOnes++;
                    queue> q;
                    q.push({i, j});
                    set> visited;
                    for (int lvl = 1; !q.empty(); lvl++) {
                        int sz = q.size();
                        while (sz--) {
                            pair curr = q.front();
                            q.pop();
                            int x = curr.first;
                            int y = curr.second;
                            for (int k = 0; k < 4; k++) {
                                int nx = x + dir[k][0];
                                int ny = y + dir[k][1];
                                if (nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0)
                                    continue;
                                visited.insert({nx, ny});
                                dist[nx][ny] += lvl;
                                reach[nx][ny]++;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0 && reach[i][j] == numberOfOnes) {
                    ret = min(ret, dist[i][j]);
                }
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

ইনপুট

[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]