लक्ष्य तक पहुँचने के लिए न्यूनतम संख्या में घूंसे खोजने के लिए C++ प्रोग्राम की आवश्यकता होती है

मान लीजिए हमारे पास एक मैट्रिक्स है जिसमें एच पंक्तियां और डब्ल्यू कॉलम हैं। कोशिकाओं में या तो '.' होता है। या '#'। बिन्दु '।' निष्क्रिय स्थान को इंगित करता है, और '#' ब्लॉक को इंगित करता है। अमल अपने घर से बाजार जाएगा। उसका घर ऊपरी-बाएँ कोने में कोठरी में है, और बाज़ार नीचे-दाएँ कोने में है। अमल एक सेल को ऊपर, नीचे, बाएँ या दाएँ एक निष्क्रिय सेल में ले जा सकता है। वह शहर नहीं छोड़ सकता। वह अवरुद्ध सेल में भी प्रवेश नहीं कर सकता है। हालाँकि, उसकी शारीरिक शक्ति उसे एक पंच के साथ अपनी पसंद के 2×2 कोशिकाओं के साथ एक वर्ग क्षेत्र में सभी ब्लॉकों को नष्ट करने की अनुमति देती है, जिससे ये कोशिकाएं निष्क्रिय हो जाती हैं। अमल के लिए बाजार तक पहुंचने के लिए हमें कम से कम घूंसे की जरूरत है।

तो, अगर इनपुट पसंद है

तो आउटपुट 1 होगा, क्योंकि हम ग्रिड को −

चिह्नित बक्सों को नष्ट करके

कदम

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

n := row count of matrix
m := column count of matrix
Define one 2D array dist of order (n + 1) x (m + 1)
Define one deque dq
insert ( 0, 0 ) at the beginning of dq
dist[0, 0] := 0
while (not dq is empty), do:
   v := first element of dq
   delete front element from dq
   for initialize i := 0, when i < 4, update (increase i by 1), do:
      x := dx[i] + v[0]
      y := dy[i] + v[1]
      if x >= 0 and x < n and y >= 0 and y < m, then:
         if matrix[x, y] is same as '.', then:
            if dist[x, y] > dist[v[0], v[1]], then:
               dist[x, y] := dist[v[0], v[1]]
               insert pair { x, y } at the beginning of dq
         Otherwise
            for initialize p := x - 1, when p <= x + 1, update (increase p by 1), do:
               for initialize q := y - 1, when q <= y + 1, update (increase q by 1), do:
                  if p >= 0 and p < n and q >= 0 and q < m, then:
                     if dist[p, q] > dist[v[0], v[1]] + 1, then:
                        dist[p, q] := dist[v[0], v[1]] + 1
                        insert pair { p, q } at the end of dq
return dist[n - 1, m - 1]

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

int solve(vector<vector<char>> matrix){
   int n = matrix.size();
   int m = matrix[0].size();
   vector<vector<int>> dist(n + 1, vector<int>(m + 1, 1e9));
   deque<array<int, 2>> dq;
   dq.push_front({ 0, 0 });
   dist[0][0] = 0;
   while (!dq.empty()){
      auto v = dq.front();
      dq.pop_front();
      for (int i = 0; i < 4; i++){
         int x = dx[i] + v[0], y = dy[i] + v[1];
         if (x >= 0 && x < n && y >= 0 && y < m){
            if (matrix[x][y] == '.'){
               if (dist[x][y] > dist[v[0]][v[1]]){
                  dist[x][y] = dist[v[0]][v[1]];
                  dq.push_front({ x, y });
               }
            } else{
               for (int p = x - 1; p <= x + 1; p++){
                  for (int q = y - 1; q <= y + 1; q++){
                     if (p >= 0 && p < n && q >= 0 && q < m){
                        if (dist[p][q] > dist[v[0]][v[1]] + 1){
                           dist[p][q] = dist[v[0]][v[1]] + 1;
                           dq.push_back({ p, q });
                        }
                     }
                  }
               }
            }
         }
      }
   }
   return dist[n - 1][m - 1];
}
int main(){
   vector<vector<char>> matrix = { { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' }, { '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, { '.', '.', '#', '.', '.' } };
   cout << solve(matrix) << endl;
}

इनपुट

{ { '.', '.', '#', '.', '.' }, { '#', '.', '#', '.', '#' },
{ '#', '#', '.', '#', '#' }, { '#', '.', '#', '.', '#' }, {
'.', '.', '#', '.', '.' } }

आउटपुट

1