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

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


मान लीजिए h × w आयाम का एक ग्रिड है। ग्रिड को 2D सरणी 'initGrid' में दर्शाया गया है, जहाँ प्रत्येक सेल या तो '#' या '.' से दर्शाई गई है। '#' का अर्थ है ग्रिड में बाधा है और '.' का अर्थ है उस सेल से पथ है। अब, एक रोबोट को ग्रिड पर सेल 'c' पर रखा गया है जिसकी पंक्ति संख्या x और स्तंभ संख्या y है। रोबोट को दूसरी सेल 'd' तक जाना है जिसकी पंक्ति संख्या p और स्तंभ संख्या q है। सेल c और d के निर्देशांक हमें पूर्णांक युग्म के रूप में दिए गए हैं। अब, रोबोट एक सेल से दूसरी सेल पर निम्न तरीकों से जा सकता है:

  • रोबोट केवल एक सेल से दूसरी सेल पर चल सकता है यदि वह सेल वर्तमान सेल से लंबवत या क्षैतिज रूप से आसन्न हो।
  • रोबोट 5×5 क्षेत्र में किसी भी सेल पर कूद सकता है जिसका केंद्र वह सेल है जहाँ वह वर्तमान में स्थित है।
  • रोबोट केवल तभी दूसरी सेल पर जा सकता है यदि गंतव्य सेल में बाधा न हो। रोबोट ग्रिड से बाहर भी नहीं जा सकता।

हमें गंतव्य तक पहुँचने के लिए आवश्यक कूद की संख्या ज्ञात करनी है।

उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, c = {2, 1}, d = {4, 4}, initGrid = {"#...", ".##.", "...#", "..#."}, तो आउटपुट 1 होगा। रोबोट को अपने गंतव्य तक पहुँचने के लिए केवल एक कूद की आवश्यकता होगी।

चरण

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

N := 100
पूर्णांक युग्म s, t परिभाषित करें
आकार N का सरणी grid परिभाषित करें
आकार N×N का सरणी dst परिभाषित करें
एक संरचना node परिभाषित करें जिसमें पूर्णांक मान a, b, e हों
एक फंक्शन check() परिभाषित करें जो a, b लेता है:
    लौटाएँ a >= 0 AND a < h AND b >= 0 AND b < w
एक फंक्शन bfs() परिभाषित करें जो a, b लेता है:
    i := 0 से h-1 तक:
        j := 0 से w-1 तक:
            dst[i][j] := अनंत
    dst[a][b] := 0
    एक डेक doubleq परिभाषित करें
    मान {a, b, dst[a][b]} वाला नोड doubleq के अंत में डालें
    जब तक doubleq खाली न हो:
        nd := doubleq का पहला तत्व
        यदि nd का e मान > dst[nd.a][nd.b], तो जारी रखें
        diffx := -2 से 2 तक:
            diffy := -2 से 2 तक:
                tm := |diffx| + |diffy|
                nx := nd.a + diffx, ny := nd.b + diffy
                यदि check(nx, ny) और grid[nx][ny] == '.', तो:
                    w := (यदि tm > 1 तो 1 अन्यथा 0)
                    यदि dst[nd.a][nd.b] + w < dst[nx][ny], तो:
                        dst[nx][ny] := dst[nd.a][nd.b] + w
                        यदि w == 0, तो:
                            मान {nx, ny, dst[nx][ny]} वाला नोड doubleq के शुरुआत में डालें
                        अन्यथा:
                            मान {nx, ny, dst[nx][ny]} वाला नोड doubleq के अंत में डालें
s := c
t := d
s के पहले मान को 1 घटाएँ
s के दूसरे मान को 1 घटाएँ
t के पहले मान को 1 घटाएँ
t के दूसरे मान को 1 घटाएँ
i := 0 से h-1 तक:
    grid[i] := initGrid[i]
bfs(s का पहला मान, s का दूसरा मान)
प्रिंट करें (यदि dst[t का पहला मान][t का दूसरा मान] == अनंत तो -1 अन्यथा dst[t का पहला मान][t का दूसरा मान])

उदाहरण

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

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; #define N 100 int h, w; pair<int, int> s, t; string grid[N]; int dst[N][N]; struct node {    int a, b, e; }; bool check(int a, int b) {    return a >= 0 && a < h && b >= 0 && b < w; } void bfs(int a, int b) {    for (int i = 0; i < h; i++) {       for (int j = 0; j < w; j++)          dst[i][j] = INF;    }    dst[a][b] = 0;    deque<node> doubleq;    doubleq.push_back({a, b, dst[a][b]});    while (!doubleq.empty()) {       node nd = doubleq.front();       doubleq.pop_front();       if (nd.e > dst[nd.a][nd.b])          continue;       for (int diffx = -2; diffx <= 2; diffx++) {          for (int diffy = -2; diffy <= 2; diffy++) {             int tm = abs(diffx) + abs(diffy);             int nx = nd.a + diffx, ny = nd.b + diffy;             if (check(nx, ny) && grid[nx][ny] == '.') {                int w = (tm > 1) ? 1 : 0;                if (dst[nd.a][nd.b] + w < dst[nx][ny]) {                   dst[nx][ny] = dst[nd.a][nd.b] + w;                   if (w == 0)                      doubleq.push_front({nx, ny, dst[nx][ny]});                   else                      doubleq.push_back({nx, ny, dst[nx][ny]});                }             }          }       }    } } void solve(pair<int,int> c, pair<int, int> d, string initGrid[]){    s = c;    t = d;    s.first--, s.second--, t.first--, t.second--;    for(int i = 0; i < h; i++)       grid[i] = initGrid[i];    bfs(s.first, s.second);    cout << (dst[t.first][t.second] == INF ? -1 :       dst[t.first][t.second]) << '\n'; } int main() {    h = 4, w = 4;    pair<int,int> c = {2, 1}, d = {4, 4};    string initGrid[] = {"#...", ".##.", "...#", "..#."}; solve(c, d, initGrid); return 0; }

इनपुट

4, 4, {2, 1}, {4, 4}, {"#...", ".##.", "...#", "..#."}

आउटपुट

1
  1. ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल स्वयं और अपने दाएँ, बाएँ, ऊपर, नीचे की सेल्स को रोशन करता है। प्रकाश सेल्स के माध्यम से चमकता है जब तक कि कोई बाधा सेल इसे न रोक दे। बाधा सेल न तो रोशन हो सकती है और न ही प्रकाश को गुजरने देती ह

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. ग्रिड में पथ बनाने के लिए ब्लॉक की जाने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में पथ बनाने के लिए ब्लॉक की जाने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड है। रोबोट सेल (0, 0) पर है और उसे (h-1, w-1) तक पहुँचना है। ग्रिड में दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। रोबोट अनब्लॉक सेल्स से गुजर सकता है लेकिन ब्लॉक सेल्स से नहीं। रोबोट चार दिशाओं में जा सकता है: बाएँ, दाएँ, ऊपर, नीचे। लेकिन रोबोट किसी सेल से दूसरी सेल म