मान लीजिए, हमें आयामों का एक ग्रिड दिया गया है h * w जिसमें दो प्रकार के सेल होते हैं, ब्लॉक और अनब्लॉक। अवरुद्ध कोशिकाओं का अर्थ है कि कोशिकाएँ पहुँच योग्य नहीं हैं और अवरोधरहित का अर्थ है कि कोशिकाएँ पहुँच योग्य हैं। हम 2डी सरणी में ग्रिड का प्रतिनिधित्व करते हैं जहां अवरुद्ध कोशिकाओं को '#' के रूप में दिया जाता है और अनब्लॉक कोशिकाओं को '।' के रूप में दिया जाता है। अब, हमें ग्रिड में एक अनब्लॉक सेल से दूसरे अनब्लॉक सेल तक पहुंचना है। हम केवल दो चालें कर सकते हैं, हम या तो लंबवत जा सकते हैं या हम क्षैतिज जा सकते हैं। हम तिरछे नहीं चल सकते। हमें यह ध्यान रखना होगा कि, हम केवल अनब्लॉक किए गए सेल में जा सकते हैं। इसलिए, हमें ग्रिड में किसी अन्य अनब्लॉक सेल से एक अनब्लॉक सेल तक पहुंचने के लिए आवश्यक चालों की अधिकतम संख्या का पता लगाना होगा।
इसलिए, यदि इनपुट h =4, w =4, grid ={"..#.", "#.#.", "..##", "###."} जैसा है, तो आउटपुट 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