C++ में The Maze II

मान लीजिए एक भूलभुलैया में खाली स्थान और दीवारों के साथ एक गेंद है। अब गेंद किसी भी दिशा जैसे ऊपर, नीचे, बाएँ या दाएँ खाली पथों से गुजर सकती है, लेकिन यह तब तक लुढ़कना बंद नहीं करेगी जब तक यह दीवार से नहीं टकराती। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है।

हमें गेंद की प्रारंभिक स्थिति, गंतव्य और भूलभुलैया दी गई है, हमें गेंद के गंतव्य पर रुकने के लिए सबसे छोटी दूरी ढूंढनी है। यहां दूरी वास्तव में खाली सेलों की संख्या से परिभाषित होती है, जो गेंद द्वारा कवर किए जाते हैं (प्रारंभिक स्थिति को छोड़कर, गंतव्य स्थिति को शामिल करके)। यदि गेंद को गंतव्य पर रोकना असंभव है, तो -1 लौटाएँ।

भूलभुलैया को एक 2D सरणी द्वारा दर्शाया गया है। यहां 1 दीवार को दर्शाता है और 0 खाली स्थान को दर्शाता है। भूलभुलैया की सीमाएँ सभी दीवारें हैं। प्रारंभ और गंतव्य निर्देशांकों को पंक्ति और स्तंभ सूचकांकों द्वारा दर्शाया गया है।

इसलिए, यदि इनपुट एक 2D सरणी द्वारा दर्शाई गई भूलभुलैया जैसा है:

प्रारंभ स्थिति (0, 4) है, गंतव्य स्थिति (4, 4) है, तो आउटपुट 12 होगा। एक संभावित तरीका है: बाएँ से नीचे से बाएँ से नीचे से दाएँ से नीचे से दाएँ। (1+1+3+1+2+2+2) = 12

समाधान दृष्टिकोण

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

• n := पंक्ति संख्या, m := स्तंभ संख्या
• ret := infinity
• क्रम n x m का एक 2D सरणी dist परिभाषित करें
• एक क्यू q परिभाषित करें
• start को q में डालें
• dist[start[0]][start[1]] := 0
• जब (q खाली नहीं है), करें:
  • curr := q का पहला तत्व
  • q से तत्व हटाएँ
  • x := curr[0], y := curr[1]
  • यदि x destination[0] के समान है और y destination[1] के समान है, तो:
    • ret := ret और dist[x][y] का न्यूनतम
  • currDist := dist[x][y]
  • tempDist := 0
  • i := x
  • जब (i + 1 < n और grid[i + 1][y] शून्य है), करें:
    • i को 1 से बढ़ाएँ
    • tempDist को 1 से बढ़ाएँ
  • यदि currDist + tempDist < dist[i][y], तो:
    • dist[i][y] := currDist + tempDist
    • { i, y } को q में डालें
  • i := x
  • tempDist := 0
  • जब (i - 1 >= 0 और grid[i - 1][y] शून्य है), करें:
    • tempDist को 1 से बढ़ाएँ
    • i को 1 से घटाएँ
  • यदि currDist + tempDist < dist[i][y], तो:
    • dist[i][y] := currDist + tempDist
    • { i, y } को q में डालें
  • i := y
  • tempDist := 0
  • जब (i - 1 >= 0 और grid[x][i - 1] शून्य है), करें:
    • i को 1 से घटाएँ
    • tempDist को 1 से बढ़ाएँ
  • यदि currDist + tempDist < dist[x][i], तो:
    • dist[x][i] := currDist + tempDist
    • { x, i } को q में डालें
  • i := y
  • tempDist := 0
  • जब (i + 1 < m और grid[x][i + 1] शून्य है), करें:
    • i को 1 से बढ़ाएँ
    • tempDist को 1 से बढ़ाएँ
  • यदि currDist + tempDist < dist[x][i], तो:
    • dist[x][i] := currDist + tempDist
    • { x, i } को q में डालें
• ret लौटाएँ (यदि ret inf के समान है, तो -1, अन्यथा ret)

उदाहरण

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

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

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid, vector<int>& start, vector<int>& destination) {
        int n = grid.size();
        int m = n ? grid[0].size() : 0;
        int ret = INT_MAX;
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        queue<vector<int>> q;
        q.push(start);
        dist[start[0]][start[1]] = 0;
        while (!q.empty()) {
            vector<int> curr = q.front();
            q.pop();
            int x = curr[0];
            int y = curr[1];
            if (x == destination[0] && y == destination[1]) {
                ret = min(ret, dist[x][y]);
            }
            int currDist = dist[x][y];
            int tempDist = 0;
            int i = x;
            while (i + 1 < n && !grid[i + 1][y]) {
                i++;
                tempDist++;
            }
            if (currDist + tempDist < dist[i][y]) {
                dist[i][y] = currDist + tempDist;
                q.push({i, y});
            }
            i = x;
            tempDist = 0;
            while (i - 1 >= 0 && !grid[i - 1][y]) {
                tempDist++;
                i--;
            }
            if (currDist + tempDist < dist[i][y]) {
                dist[i][y] = currDist + tempDist;
                q.push({i, y});
            }
            i = y;
            tempDist = 0;
            while (i - 1 >= 0 && !grid[x][i - 1]) {
                i--;
                tempDist++;
            }
            if (currDist + tempDist < dist[x][i]) {
                dist[x][i] = currDist + tempDist;
                q.push({x, i});
            }
            i = y;
            tempDist = 0;
            while (i + 1 < m && !grid[x][i + 1]) {
                i++;
                tempDist++;
            }
            if (currDist + tempDist < dist[x][i]) {
                dist[x][i] = currDist + tempDist;
                q.push({x, i});
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
    vector<int> v1 = {0,4}, v2 = {4,4};
    cout << (ob.shortestDistance(v, v1, v2));
    return 0;
}

इनपुट

{{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}}, {0,4},{4,4}

आउटपुट

12