資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢網格中被照亮的單元格數量
假設我們有一個h * w維度的網格。網格中的單元格可以包含燈泡或障礙物。一個燈泡單元格可以照亮自身以及其左右上下四個方向的單元格，光線可以穿過單元格，除非障礙物單元格阻擋了光線。障礙物單元格不能被照亮，並且它會阻止燈泡單元格的光線到達其他單元格。因此，給定網格中燈泡單元格的位置（在陣列'bulb'中）和障礙物單元格的位置（在陣列'obstacles'中），我們必須找出網格中被照亮的單元格總數。
因此，如果輸入類似於h = 4，w = 4，bulb = {{1, 1}, {2, 2}, {3, 3}}，obstacle = {{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
更新於：2022年3月2日
152 次瀏覽
廣告