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