数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用C++查找二进制矩阵中由1构成的图形的周长
在这个问题中，我们得到一个大小为n x m的二进制矩阵bin[][]，它只包含0和1。我们的任务是找到二进制矩阵中由1构成的图形的周长。
周长将从所有侧面覆盖图形，即
对于单个值1，周长为4。
让我们举个例子来理解这个问题：
输入
bin[][] = [1, 0] [1, 0]
输出
6
解释
单元格(0,0)和(1,0)连接在一起，构成一个边长为2和1的矩形。周长为6。
解决方案方法
解决这个问题的一个简单方法是简单地找到所有1及其对周长的贡献，然后将所有贡献相加以找到总周长。
1对矩阵周长的贡献是：最大贡献为4，当1单独贡献周长时；
最小贡献为0，当1被四面都是1包围时。
因此，对于矩阵的每个元素，我们需要检查它是否为1。对于所有1，我们将找到其邻居，然后计算其对周长的贡献，最后计算总周长。
程序说明了我们解决方案的工作原理：
示例
#include<iostream>
using namespace std;
#define R 3
#define C 5
int contibutionToPerimeter(int mat[][C], int i, int j) {
int neighbours = 0;
if (i > 0 && mat[i - 1][j])
neighbours++;
if (j > 0 && mat[i][j - 1])
neighbours++;
if (i < R-1 && mat[i + 1][j])
neighbours++;
if (j < C-1 && mat[i][j + 1])
neighbours++;
return (4 - neighbours);
}
int calcPerimeter(int mat[R][C]){
int perimeter = 0;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (mat[i][j] == 1)
perimeter += contibutionToPerimeter(mat, i ,j);
return perimeter;
}
int main() {
int mat[R][C] = { {0, 1, 0, 0, 0},
{1, 1, 1, 1, 0},
{1, 1, 0, 1, 1} };
cout<<"The perimeter of shapes from formed with 1s is "<<calcPerimeter(mat);
return 0;
}输出
The perimeter of shapes from formed with 1s is 18
更新于：2021年3月16日
210 次浏览
广告