ধরুন, আমাদেরকে h*w মাত্রার একটি গ্রিড দেওয়া হয়েছে যেটিতে ব্লক করা এবং আনব্লক করা দুই ধরনের সেল রয়েছে। অবরুদ্ধ কক্ষের অর্থ হল কোষগুলি অ্যাক্সেসযোগ্য নয় এবং অবরোধ মুক্ত করার অর্থ হল কোষগুলি অ্যাক্সেসযোগ্য৷ আমরা একটি 2D অ্যারেতে গ্রিডকে উপস্থাপন করি যেখানে ব্লক করা সেলগুলি '#' হিসাবে দেওয়া হয় এবং আনব্লক করা সেলগুলি '.' হিসাবে দেওয়া হয়। এখন, আমাদের একটি আনব্লক করা সেল থেকে গ্রিডের অন্য একটি আনব্লক করা ঘরে পৌঁছাতে হবে। আমরা শুধুমাত্র দুটি চাল সঞ্চালন করতে পারি, আমরা হয় উল্লম্ব যেতে পারি বা আমরা অনুভূমিক যেতে পারি। আমরা তির্যকভাবে নড়াচড়া করতে পারি না। আমাদের মনে রাখতে হবে যে, আমরা শুধুমাত্র আনব্লক করা কক্ষে যেতে পারি। সুতরাং, গ্রিডের অন্য একটি আনব্লক করা কক্ষ থেকে একটি আনব্লক করা কক্ষে পৌঁছানোর জন্য আমাদের সর্বাধিক সংখ্যক চাল খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুটটি h =4, w =4, গ্রিড ={..#.", "#.#", "..##", "###।"} হয়, তাহলে আউটপুট 4 হবে।
সেল (0,0) থেকে, সেল (2, 0) পর্যন্ত পৌঁছানোর জন্য সর্বাধিক 4টি চাল প্রয়োজন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define an array xdir of size: 4 := {1, 0, - 1, 0}
Define an array ydir of size: 4 := {0, 1, 0, - 1}
Define one 2D array dist
Define one 2D array reset
res := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
for initialize j := 0, when j < w, update (increase j by 1), do:
dist := reset
if grid[i, j] is same as '.', then:
dist[i, j] := 0
Define one queue q containing integer pairs
insert make_pair(i, j) into q
while (not q is empty), do:
x := first element of the leftmost element in the q
y := second element of the leftmost element in the q
res := maximum of (dist[x, y] and res)
delete leftmost element from q
for initialize k := 0, when k < 4, update (increase k by 1), do:
px := x + xdir[k]
py := y + ydir[k]
if px >= 0 and px < h and py >= 0 and py < w, then:
if grid[px, py] is same as '.', then:
if dist[px, py] is same as -1, then:
dist[px, py] := dist[x, y] + 1
insert pair(px, py) into q
return res উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(int h, int w, vector<string> grid){
int xdir[4] = {1, 0, -1, 0};
int ydir[4] = {0, 1, 0, -1};
vector<vector<int>> dist(h, vector<int>(w, -1));
vector<vector<int>> reset(h, vector<int>(w, -1));
int res = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
dist = reset;
if(grid[i][j] == '.'){
dist[i][j] = 0;
queue<pair<int,int>> q;
q.push(make_pair(i, j));
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
res = max(dist[x][y], res);
q.pop();
for(int k = 0; k < 4; k++){
int px = x + xdir[k];
int py = y + ydir[k];
if(px >= 0 && px < h && py >= 0 && py < w){
if(grid[px][py] == '.'){
if(dist[px][py] == -1){
dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py));
}
}
}
}
}
}
}
}
return res;
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"..#.", "#.#.", "..##", "###."};
cout << solve(h, w, grid);
return 0;
} ইনপুট
4, 4, {"..#.", "#.#.", "..##", "###."}
আউটপুট
4
