Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

लक्ष्य तक पहुंचने का रास्ता बनाने के लिए आवश्यक न्यूनतम पंच ढूंढने के लिए C++ प्रोग्राम


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

उदाहरण के लिए, यदि इनपुट है:

. . # . .
# . # . #
# # . # #
# . # . #
. . # . .

तो आउटपुट 1 होगा, क्योंकि हम ग्रिड को ऐसा बना सकते हैं:

. . # . .
# . . . #
# # . . #
# . # . #
. . # . .

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

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

n := मैट्रिक्स की पंक्ति संख्या m := मैट्रिक्स की कॉलम संख्या क्रम (n + 1) x (m + 1) का एक 2D ऐरे dist परिभाषित करें एक डीक्यू dq परिभाषित करें (0, 0) को dq की शुरुआत में डालें dist[0, 0] := 0 जब तक (dq खाली नहीं है), करें: v := dq का पहला तत्व dq से सामने का तत्व हटाएं i := 0 से 3 तक, करें: x := dx[i] + v[0] y := dy[i] + v[1] यदि x >= 0 और x < n और y >= 0 और y < m, तो: यदि matrix[x, y], '.' के बराबर है, तो: यदि dist[x, y] > dist[v[0], v[1]], तो: dist[x, y] := dist[v[0], v[1]] युग्म { x, y } को dq की शुरुआत में डालें अन्यथा p := x - 1 से x + 1 तक, करें: q := y - 1 से y + 1 तक, करें: यदि p >= 0 और p < n और q >= 0 और q < m, तो: यदि dist[p, q] > dist[v[0], v[1]] + 1, तो: dist[p, q] := dist[v[0], v[1]] + 1 युग्म { p, q } को dq के अंत में डालें 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

  1. - C++ में कुल n बनाने के लिए आवश्यक न्यूनतम अक्षरों की संख्या

    समस्या कथन एक पूर्णांक n दिया गया है और मान लें a=1, b=2, c=3, ..., z=26। कुल n बनाने के लिए आवश्यक न्यूनतम अक्षरों की संख्या ढूंढें। यदि n=23 तो आउटपुट 1 है यदि n=72 तो आउटपुट 3 है (26 + 26 + 20) एल्गोरिदम 1. यदि n 26 से विभाज्य है तो उत्तर (n/26) है 2. यदि n 26 से विभाज्य नहीं है तो उत्तर (n/26)

  1. - C++ प्रोग्राम ग्राफ को डिस्कनेक्ट करने के लिए काटने के लिए न्यूनतम एजेस की संख्या खोजने के लिए

    इस प्रोग्राम में हमें एक ग्राफ की एज कनेक्टिविटी ढूंढनी है। एक ग्राफ की एज कनेक्टिविटी का अर्थ है यह एक ब्रिज है, इसे हटाने पर ग्राफ डिस्कनेक्ट हो जाएगा। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है। फंक्शन्स और सूडोकोड connections() एक रिकर्सि

  1. - Python में अंतिम लक्ष्य तक पहुंचने के लिए आवश्यक न्यूनतम बसों की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक n x 3 मैट्रिक्स है जहां प्रत्येक पंक्ति में तीन फ़ील्ड [src, dest, id] होते हैं इसका मतलब है कि बस का रूट src से dest तक है। एक नई बस में चढ़ने के लिए एक यूनिट पैसे लगते हैं, लेकिन अगर हम उसी बस पर रहते हैं तो हमें केवल एक यूनिट देना पड़ता है। हमें स्थान 0 से अंतिम स्टॉप (सबसे