数据结构
网络
关系数据库管理系统 (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
广告