इस समस्या में, हमें nXm आकार का एक बाइनरी मैट्रिक्स बिन [] [] दिया जाता है जिसमें केवल 0 और 1 होता है। हमारा काम बाइनरी मैट्रिक्स में 1s से बनी आकृतियों की परिधि ज्ञात करना है।
लिया गया परिमाप सभी तरफ से आकृति को कवर करेगा, अर्थात
1 सिंगल मान के लिए, परिमाप 4 है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
bin[][] = [1, 0] [1, 0]
आउटपुट
6
स्पष्टीकरण
सेल (0,0) और (1, 0) भुजाओं 2 और 1 का एक आयत बनाते हुए आपस में जुड़े हुए हैं। परिमाप 6 है।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान बस एक और परिधि में उनके योगदान को ढूंढना है और फिर मूल्य खोजने के लिए सभी को जोड़ना है।
मैट्रिक्स में परिधि में 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