এই সমস্যাতে, আমাদের nXm আকারের একটি বাইনারি ম্যাট্রিক্স bin[][] দেওয়া আছে যেটি শুধু ০ এবং ১ দিয়ে গঠিত। আমাদের কাজ হলো বাইনারি ম্যাট্রিক্সে ১ দিয়ে গঠিত আকৃতির পেরিমিটার (perimeter) বের করা।
পেরিমিটার আকৃতিকে সব দিক থেকে ঘেরে থাকবে, অর্থাৎ:
একটি একক ১-এর জন্য পেরিমিটার ৪।
উদাহরণ দিয়ে সমস্যা বোঝা যাক,
ইনপুট
bin[][] = [1, 0]
[1, 0]
আউটপুট
6
ব্যাখ্যা
সেল (0,0) এবং (1, 0) সংযুক্ত থাকায় একটি আয়তাকার আকৃতি বنى যाचे যার পার্শ্ব ২ এবং ১। পেরিমিটার = ৬।
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হলো সব ১ খুঁজে বের করা এবং তাদের পেরিমিটারে অবদান (contribution) বের করে সব যোগ করা।
ম্যাট্রিক্সে একটি ১-এর পেরিমিটারে অবদান: সর্বোচ্চ অবদান ৪, যখন ১ একা পেরিমিটারে অবদান রাখে। সর্বনিম্ন অবদান ০, যখন ১ চারদিকেই ১- দিয়ে ঘেরা থাকে।
তাই, ম্যাট্রিক্সের প্রতিটি উপাদানের জন্য চেক করতে হবে যে সেটি ১ কিনা। সব ১-এর জন্য তার প্রতিবেশী (neighbours) বের করে তার পেরিমিটারে অবদান বের করব এবং শেষে মোট পেরিমিটার বের করব।
সমাধান কোড:
উদাহরণ
#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
