C++-এ Shortest Path in Binary Matrix

ধরি আমাদের একটি N x N স্কয়ার গ্রিড আছে, যেখানে প্রতিটি সেল হয় খালি (0) অথবা ব্লকড (1)। একটি ক্লিয়ার পাথ টপ-লেফট থেকে বটম-রাইট পর্যন্ত দৈর্ঘ্য k-র হবে যদি এবং কেবল যদি সেটি C_1, C_2, ..., C_k সেলগুলোর কম্পোজিশন থাকে যাতে:

• এডজাসেন্ট সেল C_i এবং C_{i+1} ৮-ডিরেকশনালি কানেক্টেড (তাই সেগুলো আলাদা এবং একটি এজ বা কর্নার শেয়ার করে)

• C_1 লোকেশন (0, 0)-এ অবস্থিত

• C_k লোকেশন (N-1, N-1)-এ অবস্থিত

• যদি C_i (r, c)-এ অবস্থিত হয়, তবে grid[r][c] খালি বা 0 ধারণ করে

আমাদের টপ-লেফট থেকে বটম-রাইট পর্যন্ত সবচেয়ে ছোট যেকোনো ক্লিয়ার পাথের দৈর্ঘ্য বের করতে হবে। যদি এমন কোনো পাথ না থাকে, তবে -1 রিটার্ন করুন।

উদাহরণস্বরূপ, যদি গ্রিড নিচের মত হয়:

অরেঞ্জ সেলগুলো পাথ হবে। দৈর্ঘ্য ৪।

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

• একটি ডিরেকশন অ্যারে ডিফাইন করুন, এটি ৮টি পেয়ার ধারণ করবে ৮টি ভিন্ন ডিরেকশনে মুভ করার জন্য। অ্যারেটি হবে [[1,1], [1,-1], [-1,1], [1,0], [0,1], [-1,-1], [0,-1], [-1,0]]

• মেইন সেকশন গ্রিডকে ইনপুট হিসেবে নিবে, এটি নিচের মত কাজ করবে:

• একটি পয়েন্টের কিউ q ডিফাইন করুন, n := সারি সংখ্যা

• যদি grid[0][0] 0 হয়, তবে একটি নতুন পয়েন্ট p(0, 0, 1) তৈরি করুন, p কিউ-তে ইনসার্ট করুন, এবং grid[0][0] := 1 সেট করুন

• যখন পর্যন্ত q খালি নয়

  • curr := q থেকে ফ্রন্ট পয়েন্ট, q থেকে ফ্রন্ট পয়েন্ট ডিলিট করুন

  • x := curr.x, y := curr.y, c := curr.c

  • যদি x = n-1 এবং y = n-1 হয়, তবে c রিটার্ন করুন

  • c ১ বাড়ান

  • i = 0 থেকে 7 পর্যন্ত লুপ চালান

    • X := x + d[i][0], Y := y + d[i][1]

    • যদি X 0 এবং n-র রেঞ্জে থাকে এবং Y 0 এবং n-র রেঞ্জে থাকে, এবং grid[X][Y] 0 হয়, তবে

      • grid[X][Y] := 1

      • q-তে একটি নতুন পয়েন্ট p(X, Y, c) ইনসার্ট করুন

• -1 রিটার্ন করুন

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:

উদাহরণ

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

int d[8][2] = {{1, 1}, {1, -1}, {-1, 1}, {1, 0}, {0, 1}, {-1, -1}, {0, -1}, {-1, 0}};

struct point {
    int x, y, c;
    point(int a, int b, int z) {
        x = a;
        y = b;
        c = z;
    }
};

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        queue<point> q;
        int n = grid.size();
        if(!grid[0][0]) {
            q.push(point(0, 0, 1));
            grid[0][0] = 1;
        }
        while(!q.empty()) {
            point curr = q.front();
            q.pop();
            int x = curr.x;
            int y = curr.y;
            int c = curr.c;
            if(x == n-1 && y == n-1) return c;
            c++;
            for(int i = 0; i < 8; i++) {
                int X = x + d[i][0];
                int Y = y + d[i][1];
                if(X >= 0 && X < n && Y >= 0 && Y < n && !grid[X][Y]) {
                    grid[X][Y] = 1;
                    q.push(point(X, Y, c));
                }
            }
        }
        return -1;
    }
};

int main() {
    vector<vector<int>> v = {{0,0,0},{1,1,0},{1,1,0}};
    Solution ob;
    cout << (ob.shortestPathBinaryMatrix(v));
}

ইনপুট

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

আউটপুট

4