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

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


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

उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}}, तो आउटपुट 13 होगा।

छवि से हम ग्रिड में रोशन सेल्स देख सकते हैं।

चरण

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

bulbSize := bulb का आकार
blockSize := obstacle का आकार
एक 2D सरणी grid परिभाषित करें
i := 0 से bulbSize-1 तक:
    x := bulb[i] का पहला मान
    y := bulb[i] का दूसरा मान
    grid[x][y] := 1
i := 0 से blockSize-1 तक:
    x := obstacle[i] का पहला मान
    y := obstacle[i] का दूसरा मान
    grid[x][y] := 2
result := h * w
एक 2D सरणी check परिभाषित करें
i := 0 से h-1 तक:
    gd := 0
    j := 0 से w-1 तक:
        यदि grid[i][j] == 2, तो gd := 0
        यदि grid[i][j] == 1, तो gd := 1
        check[i][j] := check[i][j] OR gd
    gd := 0
    j := w-1 से 0 तक:
        यदि grid[i][j] == 2, तो gd := 0
        यदि grid[i][j] == 1, तो gd := 1
        check[i][j] := check[i][j] OR gd
j := 0 से w-1 तक:
    k := 0
    i := 0 से h-1 तक:
        यदि grid[i][j] == 2, तो k := 0
        यदि grid[i][j] == 1, तो k := 1
        check[i][j] := check[i][j] OR k
    k := 0
    i := h-1 से 0 तक:
        यदि grid[i][j] == 2, तो k := 0
        यदि grid[i][j] == 1, तो k := 1
        check[i][j] := check[i][j] OR k
i := 0 से h-1 तक:
    j := 0 से w-1 तक:
        result := result - NOT(check[i][j])
result लौटाएँ

उदाहरण

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

#include <bits/stdc++.h> using namespace std; int solve(int h, int w, vector<pair<int, int>> bulb, vector<pair<int, int>> obstacle){    int bulbSize = bulb.size();    int blockSize = obstacle.size();    vector<vector<int>> grid(h, vector<int>(w, 0));    for (int i = 0; i < bulbSize; i++) {       int x = bulb[i].first;       int y = bulb[i].second;       grid[x][y] = 1;    }    for (int i = 0; i < blockSize; i++) {       int x = obstacle[i].first;       int y = obstacle[i].second;       grid[x][y] = 2;    }    int result = h * w;    vector<vector<bool>> check(h, vector<bool>(w, 0));    for (int i = 0; i < h; i++) {       bool gd = 0;       for (int j = 0; j < w; j++) {          if (grid[i][j] == 2)             gd = 0;          if (grid[i][j] == 1)             gd = 1;          check[i][j] = check[i][j] | gd;       }       gd = 0;       for (int j = w - 1; j >= 0; j--) {          if (grid[i][j] == 2)             gd = 0;          if (grid[i][j] == 1)             gd = 1;          check[i][j] = check[i][j] | gd;       }    }    for (int j = 0; j < w; j++) {       bool k = 0;       for (int i = 0; i < h; i++) {          if (grid[i][j] == 2)             k = 0;          if (grid[i][j] == 1)             k = 1;          check[i][j] = check[i][j] | k;       }       k = 0;       for (int i = h - 1; i >= 0; i--) {          if (grid[i][j] == 2)             k = 0;          if (grid[i][j] == 1) k = 1;         check[i][j] = check[i][j] | k; } } for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) result -= !check[i][j]; return result; } int main() { int h = 4, w = 4; vector<pair<int, int>> bulb = {{1, 1}, {2, 2}, {3, 3}}, obstacle = {{0, 0}, {2, 3}}; cout<< solve(h, w, bulb, obstacle); return 0; }

इनपुट

4, 4, {{1, 1}, {2, 2}, {3, 3}}, {{0, 0}, {2, 3}}

आउटपुट

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

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

  1. - सरणी में दिए गए शर्त को पूरा करने वाले युग्मों की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए nums सरणी में n संख्याएँ दी गई हैं। हमें सरणी से दो संख्याओं का एक युग्म चुनना है, और शर्त यह है कि सरणी में उनकी स्थितियों का अंतर दोनों संख्याओं के योग के बराबर हो। दी गई सरणी से कुल n(n-1)/2 युग्म बन सकते हैं। हमें ऐसे युग्मों की कुल संख्या ज्ञात करनी है। उदाहरण के लिए, यदि इनपुट है n

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

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