पथ बनाने के लिए ग्रिड में ब्लॉक करने के लिए कोशिकाओं की संख्या का पता लगाने के लिए सी ++ प्रोग्राम

मान लीजिए, h * w आयामों का एक ग्रिड है। सेल स्थिति (0, 0) में एक रोबोट है और उसे स्थिति (h-1, w-1) पर जाना है। एक ग्रिड में दो प्रकार के सेल होते हैं, ब्लॉक और अनब्लॉक। रोबोट अनब्लॉक की गई कोशिकाओं से गुजर सकता है लेकिन अवरुद्ध कोशिकाओं से नहीं गुजर सकता। रोबोट चार दिशाओं में जा सकता है; यह बाएँ, दाएँ, ऊपर और नीचे जा सकता है। लेकिन रोबोट एक सेल से दूसरी सेल में किसी भी दिशा में जा सकता है (पिछले सेल को अनदेखा कर रहा है), इसलिए हमें केवल एक पथ बनाना होगा और अन्य सभी कोशिकाओं को ब्लॉक करना होगा जो उस पथ में नहीं हैं। हमें पता लगाना है और लौटाना है कि रोबोट के लिए (0, 0) से (h-1, w-1) तक एक पथ बनाने के लिए हमें कितनी कोशिकाओं को ब्लॉक करना है और यदि कोई पथ संभव नहीं है, तो हम -1 लौटते हैं।

इसलिए, यदि इनपुट h =4, w =4, ग्रिड ={"..#", "#.#.", "#.##", "#..."} जैसा है, तो आउटपुट 2 होगा।

(0, 0) से (3, 3) तक का एकल पथ बनाने के लिए हमें केवल दो कक्षों को ब्लॉक करना होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

Define one 2D array dp
dp[0, 0] := 0
Define an array moves containing pairs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
Define one queue q
insert pair (0, 0) at the end of q
while (not q is empty), do:
   p := first element of q
   delete first element from q
   for initialize i := 0, when i < 4, update (increase i by 1), do:
      row := first value of p + first value of moves[i]
      col := second value of p + second value of moves[i]
      if row < 0 or row > h - 1 or col < 0 or col > w - 1, then:
         Ignore following part, skip to the next iteration
      if grid[row, col] is same as '#', then:
         Ignore following part, skip to the next iteration
      if dp[first value of p, second value of p] + 1 < dp[row, col], then:
         dp[row, col] := dp[first value of p, second value of p] + 1
         insert pair(row, col) into q
if dp[h - 1, w - 1] is same as 2500, then:
   return -1
count := 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:
      if grid[i, j] is same as '.', then:
         (increase count by 1)
return 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, {"..#.", "#.#.", "#.##", "#..."}