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

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


मान लीजिए x × y आयाम का एक ग्रिड दिया गया है जिसमें दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। ब्लॉक सेल पहुँच योग्य नहीं हैं और अनब्लॉक पहुँच योग्य हैं। ग्रिड को 2D सरणी में दर्शाया गया है जहाँ ब्लॉक सेल '#' और अनब्लॉक सेल '.' से दर्शाए गए हैं। अब हमें सेल (0, 0) से सेल (x, y) तक पहुँचना है। हम केवल दो चालें कर सकते हैं: किसी सेल के दाएँ जाना या किसी सेल से नीचे जाना। ध्यान रखें कि हम केवल अनब्लॉक सेल्स पर जा सकते हैं, और (0, 0) और (x, y) दोनों अनब्लॉक हैं। यदि हम (0, 0) से (x, y) नहीं पहुँच सकते, तो हम ब्लॉक सेल को अनब्लॉक बना सकते हैं। हमें गंतव्य तक पहुँचने के लिए आवश्यक न्यूनतम परिवर्तन ऑपरेशन्स की संख्या ज्ञात करनी है।

उदाहरण के लिए, यदि इनपुट है x = 4, y = 4, grid = {"..#.", "#.#.", "#.##", "###."}, तो आउटपुट 1 होगा।

केवल एक परिवर्तन ऑपरेशन करना होगा। यदि हम सेल (2, 2) को ब्लॉक से अनब्लॉक में बदल दें, तो हम (0, 0) से (3, 3) पहुँच सकते हैं।

चरण

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

एक 2D सरणी mat परिभाषित करें
यदि grid[0][0] == '#', तो mat[0][0] := 1 अन्यथा mat[0][0] := 0
i := 0 से x-1 तक:
    j := 0 से y-1 तक:
        यदि i+1 < x, तो:
            mat[i+1][j] = min(mat[i+1][j], mat[i][j] + (1 यदि grid[i+1][j]=='#' और grid[i][j]=='.'))
        यदि j+1 < y, तो:
            mat[i][j+1] = min(mat[i][j+1], mat[i][j] + (1 यदि grid[i][j+1]=='#' और grid[i][j]=='.'))
mat[x-1][y-1] लौटाएँ

उदाहरण

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

#include <bits/stdc++.h> using namespace std; int solve(int x, int y, vector<string> grid){    vector<vector<int>> mat(x, vector<int>(y, 100));    if(grid[0][0] == '#')       mat[0][0] = 1;    else       mat[0][0] = 0;    for(int i = 0; i < x; i++){       for(int j = 0; j < y; j++){          if(i + 1 < x){             mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.'));          }          if(j + 1 < y){             mat[i][j + 1] = min(mat[i][j + 1],mat[i][j]+(grid[i][j + 1] == '#' && grid[i][j] == '.'));          }       }    }    return mat[x - 1][y - 1]; } int main() {    int x = 4, y = 4;   vector<string> grid = {"..#.", "#.#.", "#.##", "###."}; cout<< solve(x, y, grid); return 0; }

इनपुट

4, 4, {"..#.", "#.#.", "#.##", "###."}

आउटपुट

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

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

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

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

  1. C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम C++ में प्रतिद्वंद्वी को पकड़ने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढने का प्रोग्राम

    परिचय मान लीजिए हमारे पास ट्री एजेज की एक सूची है [u, v] के रूप में, जो इंगित करती है कि u और v के बीच एक अनडायरेक्टेड एज है। और हमारे पास दो मान x और y भी हैं। यदि हम नोड x पर हैं, और हमारा प्रतिद्वंद्वी नोड y पर है। पहले राउंड में हम चलते हैं, फिर अगले राउंड में प्रतिद्वंद्वी चलता है और इसी तरह।