मान लीजिए h × w आयाम का एक ग्रिड दिया गया है जिसमें दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। ब्लॉक सेल का अर्थ है पहुँच योग्य नहीं और अनब्लॉक का अर्थ है पहुँच योग्य। ग्रिड को 2D सरणी में दर्शाया गया है जहाँ ब्लॉक सेल '#' और अनब्लॉक सेल '.' से दर्शाए गए हैं। अब हमें ग्रिड में एक अनब्लॉक सेल से दूसरी अनब्लॉक सेल तक पहुँचना है। हम केवल दो चालें कर सकते हैं: लंबवत या क्षैतिज। तिरछे नहीं चल सकते। ध्यान रखें कि हम केवल अनब्लॉक सेल्स पर जा सकते हैं। हमें ग्रिड में एक अनब्लॉक सेल से दूसरी अनब्लॉक सेल तक पहुँचने के लिए आवश्यक अधिकतम चालों की संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, grid = {"..#.", "#.#.", "..##", "###."}, तो आउटपुट 4 होगा।
सेल (0,0) से सेल (2, 0) तक पहुँचने के लिए अधिकतम 4 चालें आवश्यक हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
आकार 4 के सरणी xdir := {1, 0, -1, 0} परिभाषित करें
आकार 4 के सरणी ydir := {0, 1, 0, -1} परिभाषित करें
एक 2D सरणी dist परिभाषित करें
एक 2D सरणी reset परिभाषित करें
res := 0
i := 0 से h-1 तक:
j := 0 से w-1 तक:
dist := reset
यदि grid[i][j] == '.', तो:
dist[i][j] := 0
पूर्णांक युग्मों वाली कतार q परिभाषित करें
q में make_pair(i, j) डालें
जब तक q खाली न हो:
x := q के बाएँ तत्व का पहला मान
y := q के बाएँ तत्व का दूसरा मान
res := max(dist[x][y], res)
q से बाएँ तत्व हटाएँ
k := 0 से 3 तक:
px := x + xdir[k]
py := y + ydir[k]
यदि px >= 0 और px < h और py >= 0 और py < w, तो:
यदि grid[px][py] == '.', तो:
यदि dist[px][py] == -1, तो:
dist[px][py] := dist[x][y] + 1
q में युग्म (px, py) डालें
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
