資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式：找出可照亮的最大單元格數
假設我們有一個h * w維的網格。網格中的單元格可以包含燈泡或障礙物。燈泡單元格會照亮其左右、上下方向的單元格，除非障礙物單元格阻擋了光線。障礙物單元格無法被照亮，並且它會阻止燈泡單元格的光線到達其他單元格。網格用字串陣列給出，其中“#”表示障礙物，“.”表示空單元格。我們只有一個燈泡，我們必須找出透過最佳放置燈泡可以照亮的最大單元格數。
因此，如果輸入為h = 4，w = 4，grid = {"#...", "....", "...#", "...."}，則輸出為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, {"#...", "....", "...#", "...."}輸出
7
更新於：2022年3月2日
瀏覽量：183
廣告