Giả sử, chúng ta được cung cấp một lưới có kích thước h * w. Các ô trong lưới có thể chứa bóng đèn hoặc chướng ngại vật. Một ô bóng đèn tự chiếu sáng và các ô ở bên phải, bên trái, lên và xuống của nó và ánh sáng có thể chiếu qua các ô trừ khi một ô vật cản cản ánh sáng. Một ô chướng ngại vật không thể được chiếu sáng và nó chặn ánh sáng từ một ô bóng đèn đến các ô khác. Vì vậy, với vị trí của các ô bóng đèn trong lưới trong mảng 'bóng đèn' và vị trí của các ô chướng ngại vật trong mảng 'chướng ngại vật', chúng ta phải tìm ra tổng số ô trong lưới được chiếu sáng.
Vì vậy, nếu đầu vào giống như h =4, w =4, bóng đèn ={{1, 1}, {2, 2}, {3, 3}}, chướng ngại vật ={{0, 0}, {2, 3 }}, thì đầu ra sẽ là 13.
Từ hình ảnh, chúng ta có thể thấy các ô được chiếu sáng trong lưới.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
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 Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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;
} Đầu vào
4, 4, {{1, 1}, {2, 2}, {3, 3}}, {{0, 0}, {2, 3}}
Đầu ra
13