मान लीजिए h × w आयाम का एक ग्रिड है। रोबोट सेल (0, 0) पर है और उसे (h-1, w-1) तक पहुँचना है। ग्रिड में दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। रोबोट अनब्लॉक सेल्स से गुजर सकता है लेकिन ब्लॉक सेल्स से नहीं। रोबोट चार दिशाओं में जा सकता है: बाएँ, दाएँ, ऊपर, नीचे। लेकिन रोबोट किसी सेल से दूसरी सेल में किसी भी दिशा में जा सकता है (पिछली सेल को नजरअंदाज करते हुए), इसलिए हमें केवल एक पथ बनाना है और उस पथ में नहीं आने वाली अन्य सभी सेल्स को ब्लॉक करना है। हमें ज्ञात करना है कि (0, 0) से (h-1, w-1) तक रोबोट के लिए एकल पथ बनाने के लिए कितनी सेल्स ब्लॉक करनी होंगी और यदि कोई पथ संभव नहीं है तो -1 लौटाएँ।
उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, grid = {"..#.", "#.#.", "#.##", "#..."}, तो आउटपुट 2 होगा।
(0, 0) से (3, 3) तक एकल पथ बनाने के लिए केवल दो सेल्स ब्लॉक करनी होंगी।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक 2D सरणी dp परिभाषित करें
dp[0][0] := 0
युग्मों वाला सरणी moves := {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
एक कतार q परिभाषित करें
q में युग्म (0, 0) डालें
जब तक q खाली न हो:
p := q का पहला तत्व
q से पहला तत्व हटाएँ
i := 0 से 3 तक:
row := p.first + moves[i].first
col := p.second + moves[i].second
यदि row < 0 या row > h-1 या col < 0 या col > w-1, तो जारी रखें
यदि grid[row][col] == '#', तो जारी रखें
यदि dp[p.first][p.second] + 1 < dp[row][col], तो:
dp[row][col] := dp[p.first][p.second] + 1
q में युग्म (row, col) डालें
यदि dp[h-1][w-1] == 2500, तो -1 लौटाएँ
count := 0
i := 0 से h-1 तक:
j := 0 से w-1 तक:
यदि grid[i][j] == '.', तो count बढ़ाएँ
count - (dp[h-1][w-1] + 1) लौटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(int h, int w, vector<string> grid){ vector<vector<int>> dp(h, vector<int>(w, 2500)); dp[0][0] = 0; vector<pair<int, int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; queue<pair<int, int>> q; q.push(make_pair(0, 0)); while (!q.empty()) { auto p = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int row = p.first + moves[i].first; int col = p.second + moves[i].second; if (row < 0 || row > h - 1 || col < 0 || col > w - 1) continue; if (grid[row][col] == '#') continue; if (dp[p.first][p.second] + 1 < dp[row][col]) { dp[row][col] = dp[p.first][p.second] + 1; q.push(make_pair(row, col)); } } } if (dp[h - 1][w - 1] == 2500) { return -1; } int count = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (grid[i][j] == '.') count++; } } return count - (dp[h - 1][w - 1] + 1); } int main() { int h = 4, w = 4; vector<string> grid = {"..#.", "#.#.", "#.##", "#..."}; cout<< solve(h, w, grid); return 0; }
इनपुट
4, 4, {"..#.", "#.#.", "#.##", "#..."}
आउटपुट
2
