数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找网格中多边形的边数
假设我们给定一个维度为h x w的网格。网格中有两种类型的单元格：白色单元格和黑色单元格。白色单元格用'.'表示，黑色单元格用'#'表示。现在网格中有多个黑色单元格构成一个多边形。我们必须找出多边形的边数。需要注意的是，网格的最外层单元格始终是白色的。
因此，如果输入如下：h = 4，w = 4，grid = {"....", ".##.", ".##.", "...."}，则输出为4。
黑色单元格构成一个正方形，正方形有4条边。
步骤
为了解决这个问题，我们将遵循以下步骤：
sides := 0 for initialize i := 1, when i < h, update (increase i by 1), do: for initialize j := 1, when j < w, update (increase j by 1), do: bl := 0 if grid[i - 1, j - 1] is same as '#', then: (increase bl by 1) if grid[i - 1, j] is same as '#', then: (increase bl by 1) if grid[i, j - 1] is same as '#', then: (increase bl by 1) if grid[i, j] is same as '#', then: (increase bl by 1) if bl is same as 1 or 3, then: (increase sides by 1) return sides
示例
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
void solve(int h, int w, vector<string> grid){
int sides = 0;
for(int i = 1; i < h; i++) {
for(int j = 1; j < w; j++) {
int bl = 0;
if(grid.at(i - 1).at(j - 1) == '#') {
bl++;
}
if(grid.at(i - 1).at(j) == '#') {
bl++;
}
if(grid.at(i).at(j - 1) == '#') {
bl++;
}
if(grid.at(i).at(j) == '#') {
bl++;
}
if(bl == 1 or bl == 3) {
sides++;
}
}
}
cout << sides;
}
int main() {
int h = 4, w = 4;
vector<string> grid = {"....", ".##.", ".##.", "...."};
solve(h, w, grid);
return 0;
}输入
4, 4, {"....", ".##.", ".##.", "...."}输出
4
更新于：2022年3月2日
309 次浏览
广告