C++ प्रोग्राम अधिकतम संख्या में कक्षों का पता लगाने के लिए जिन्हें प्रकाशित किया जा सकता है

मान लीजिए, हमें h * w आयामों का एक ग्रिड दिया गया है। ग्रिड में कोशिकाओं में या तो एक बल्ब या बाधाएं हो सकती हैं। एक लाइट बल्ब सेल अपने दाएं, बाएं, ऊपर और नीचे की कोशिकाओं को रोशन करता है और प्रकाश कोशिकाओं के माध्यम से चमक सकता है जब तक कि कोई बाधा सेल प्रकाश को अवरुद्ध न करे। एक बाधा सेल को रोशन नहीं किया जा सकता है और यह एक बल्ब सेल से प्रकाश को अन्य कोशिकाओं तक पहुंचने से रोकता है। हमें स्ट्रिंग्स की एक सरणी में ग्रिड दिया गया है, जहां '#' एक बाधा का प्रतिनिधित्व करता है और '।' एक खाली सेल का प्रतिनिधित्व करता है। हमारे पास केवल एक बल्ब है और हमें ग्रिड में बल्ब को बेहतर ढंग से रखकर अधिकतम संख्या में सेल का पता लगाना है जिससे हम रोशन कर सकें।

इसलिए, यदि इनपुट h =4, w =4, ग्रिड ={"#...", "...", "...#", "...."} जैसा है, तो आउटपुट 7 होगा।

छवि से, हम ग्रिड में प्रबुद्ध कोशिकाओं को देख सकते हैं।

कदम

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

Define one 2D array first
for initialize i := 0, when i < h, update (increase i by 1), do:
   count := 0
   for initialize j := 0, when j < w, update (increase j by 1), do:
      if grid[i, j] is same as '#', then:
         count := 0
         Ignore following part, skip to the next iteration
      else:
         first[i, j] := count
         (increase count by 1)
   k := 0
   for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
      if grid[i, j] is same as '#', then:
         k := 0
        Ignore following part, skip to the next iteration
     else:
        k := maximum of k and first[i, j]
        first[i, j] := k
Define one 2D array second
for initialize j := 0, when j < w, update (increase j by 1), do:
   count := 0
   for initialize i := 0, when i < h, update (increase i by 1), do:
      if grid[i, j] is same as '#', then:
         count := 0
         Ignore following part, skip to the next iteration
      else:
         second[i, j] := count
         (increase count by 1)
k := 0
for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
   if grid[i, j] is same as '#', then:
      k := 0
      Ignore following part, skip to the next iteration
   else:
      k := maximum of k and second[i, j]
      second[i, j] := k
result := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      result := maximum of result and first[i, j] + second[i, j]
return result + 1

उदाहरण

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

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

int solve(int h, int w, vector<string> grid){
   vector<vector<int>> first(h, vector<int> (w));
   for(int i = 0; i < h; i++) {
      int count = 0;
      for(int j = 0; j < w; j++) {
         if(grid[i][j] == '#') {
            count = 0;
            continue;
         } else {
            first[i][j] = count;
            count++;
         }
      }
      int k = 0;
      for(int j = w-1; j >= 0; j--) {
         if(grid[i][j] == '#') {
            k = 0;
            continue;
         } else {
            k = max(k, first[i][j]);
            first[i][j] = k;
         }
      }
   }
   vector<vector<int>> second(h, vector<int> (w));
   for(int j = 0; j < w; j++) {
      int count = 0;
      for(int i = 0; i < h; i++) {
         if(grid[i][j] == '#') {
            count = 0;
            continue;
         } else {
            second[i][j] = count;
            count++;
         }
      }
      int k = 0;
      for(int i = h-1; i >= 0; i--) {
         if(grid[i][j] == '#') {
            k = 0;
            continue;
         } else {
            k = max(k, second[i][j]);
            second[i][j] = k;
         }
       }
    }
    int result = 0;
    for(int i = 0; i < h; i++) {
       for(int j = 0; j < w; j++) {
          result = max(result, first[i][j] + second[i][j]);
       }
    }
    return result + 1;
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"#...", "....", "...#", "...."};
   cout<< solve(h, w, grid);
   return 0;
}

इनपुट

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