मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल अपने दाएँ, बाएँ, ऊपर और नीचे की सेल्स को रोशन करता है और प्रकाश सेल्स के माध्यम से चमक सकता है जब तक कि कोई बाधा सेल प्रकाश को न रोक दे। बाधा सेल को रोशन नहीं किया जा सकता और यह बल्ब के प्रकाश को अन्य सेल्स तक पहुँचने से रोकता है। ग्रिड को स्ट्रिंग्स की सरणी के रूप में दिया गया है जहाँ '#' बाधा दर्शाता है और '.' रिक्त सेल दर्शाता है। हमारे पास केवल एक बल्ब है और हमें ग्रिड में बल्ब को इष्टतम स्थान पर रखकर अधिकतम रोशन की जा सकने वाली सेल्स की संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है h = 4, w = 4, grid = {"#...", "....", "...#", "...."}, तो आउटपुट 7 होगा।
छवि से हम ग्रिड में रोशन सेल्स देख सकते हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
एक 2D सरणी first परिभाषित करें
i := 0 से h-1 तक:
count := 0
j := 0 से w-1 तक:
यदि grid[i][j] == '#', तो:
count := 0
जारी रखें
अन्यथा:
first[i][j] := count
count बढ़ाएँ
k := 0
j := w-1 से 0 तक घटाते हुए:
यदि grid[i][j] == '#', तो:
k := 0
जारी रखें
अन्यथा:
k := max(k, first[i][j])
first[i][j] := k
एक 2D सरणी second परिभाषित करें
j := 0 से w-1 तक:
count := 0
i := 0 से h-1 तक:
यदि grid[i][j] == '#', तो:
count := 0
जारी रखें
अन्यथा:
second[i][j] := count
count बढ़ाएँ
k := 0
i := h-1 से 0 तक घटाते हुए:
यदि grid[i][j] == '#', तो:
k := 0
जारी रखें
अन्यथा:
k := max(k, second[i][j])
second[i][j] := k
result := 0
i := 0 से h-1 तक:
j := 0 से w-1 तक:
result := max(result, first[i][j] + second[i][j])
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, {"#...", "....", "...#", "...."}
आउटपुट
7
