資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告