मान लीजिए, हमें h * w आयामों का एक ग्रिड दिया गया है। ग्रिड में कोशिकाओं में या तो बल्ब या बाधाएं हो सकती हैं। एक लाइट बल्ब सेल स्वयं को और उसके दाएं, बाएं, ऊपर और नीचे की कोशिकाओं को रोशन करता है और प्रकाश कोशिकाओं के माध्यम से चमक सकता है जब तक कि कोई बाधा सेल प्रकाश को अवरुद्ध न करे। एक बाधा सेल को प्रकाशित नहीं किया जा सकता है और यह एक बल्ब सेल से प्रकाश को अन्य कोशिकाओं तक पहुंचने से रोकता है। तो, सरणी 'बल्ब' में ग्रिड में बल्ब कोशिकाओं की स्थिति और सरणी 'बाधाओं' में बाधा कोशिकाओं की स्थिति को देखते हुए, हमें ग्रिड में प्रकाशित कोशिकाओं की कुल संख्या का पता लगाना होगा।
अतः, यदि इनपुट h =4, w =4, बल्ब ={{1, 1}, {2, 2}, {3, 3}}, बाधा ={{0, 0}, {2, 3 }}, तो आउटपुट 13 होगा।
छवि से, हम ग्रिड में प्रबुद्ध कोशिकाओं को देख सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
bulbSize := size of bulb
blockSize := size of obstacle
Define one 2D array grid
for initialize i := 0, when i < bulbSize, update (increase i by 1), do:
x := first value of bulb[i]
y := second value of bulb[i]
grid[x, y] := 1
for initialize i := 0, when i < blockSize, update (increase i by 1), do:
x := first value of obstacle[i]
y := first value of obstacle[i]
grid[x, y] := 2
result := h * w
Define one 2D array check
for initialize i := 0, when i < h, update (increase i by 1), do:
gd := 0
for initialize j := 0, when j < w, update (increase j by 1), do:
if grid[i, j] is same as 2, then:
gd := 0
if grid[i, j] is same as 1, then:
gd := 1
check[i, j] := check[i, j] OR gd
gd := 0
for initialize j := w - 1, when j >= 0, update (decrease j by 1), do:
if grid[i, j] is same as 2, then:
gd := 0
if grid[i, j] is same as 1, then:
gd := 1
check[i, j] := check[i, j] OR gd
for initialize j := 0, when j < w, update (increase j by 1), do:
k := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
if grid[i, j] is same as 2, then:
k := 0
if grid[i, j] is same as 1, then:
k := 1
check[i, j] := check[i, j] OR k
k := 0
for initialize i := h - 1, when i >= 0, update (decrease i by 1), do:
if grid[i, j] is same as 2, then:
k := 0
if grid[i, j] is same as 1, then:
k := 1
check[i, j] := check[i, j] OR k
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 := result - NOT(check[i, j])
return 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