এই সমস্যায়, আমাদের দুটি ডাইমেনশনাল অ্যারে mat[n][m] দেওয়া আছে। আমাদের কাজ হল ম্যাট্রিক্সে এন্ডলেস পয়েন্টের সংখ্যা খুঁজে বের করা।
ম্যাট্রিক্সের যেকোনো পয়েন্টকে এন্ডলেস বলা হয় যদি তার পরবর্তী সব এলিমেন্ট ১ হয়। অর্থাৎ:
mat[i][j] এন্ডলেস যখন mat[i+1][j] … mat[n][j] এবং mat[i][j+1] … mat[i][m] সব ১।
উদাহরণ
ইনপুট
mat[][] = {{0, 0}, {1, 1}}
আউটপুট
2
ব্যাখ্যা
এলিমেন্ট mat[0][1] এবং mat[1][1] হল এন্ডলেস।
সমাধানের পদ্ধতি
এই সমস্যার সহজ সমাধান হল ম্যাট্রিক্সের সব এলিমেন্টের ওপর ইটারেট করা। এবং প্রতিটি এলিমেন্টের জন্য চেক করা যে বর্তমান এলিমেন্ট এন্ডলেস কিনা। যদি হয়, তবে কাউন্ট বাড়ান। সকল এলিমেন্ট চেক করার পর কাউন্ট রিটার্ন করুন।
দক্ষ পদ্ধতি (ডাইনামিক প্রোগ্রামিং)
সমস্যাটি সমাধানের জন্য, আমরা ডাইনামিক প্রোগ্রামিং ব্যবহার করব এন্ডলেস এলিমেন্ট চেক করার জন্য। এন্ডলেস হলে সেটার সারি ও কলামের সব পরবর্তী এলিমেন্ট ১ হতে হবে।
সুতরাং, আমরা দুটি DP ম্যাট্রিক্স ব্যবহার করব প্রতিটি ইন্ডেক্সের জন্য এন্ডলেস নেক্সট সারি ও এন্ডলেস নেক্সট কলাম গণনা করার জন্য। এবং প্রতিটি পজিশন চেক করব, যদি পজিশনে নেক্সট এন্ডলেস সারি ও কলাম থাকে। তারপর এন্ডলেস এলিমেন্টের কাউন্ট রিটার্ন করব।
প্রোগ্রাম উদাহরণ
#include <iostream>
#include <math.h>
using namespace std;
const int monthDays[12] = { 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 };
int countLeapYearDays(int d[]){
int years = d[2];
if (d[1] <= 2)
years--;
return ((years / 4) - (years / 100) + (years / 400));
}
int countNoOfDays(int date1[], int date2[]){
long int dayCount1 = (date1[2] * 365);
dayCount1 += monthDays[date1[1]];
dayCount1 += date1[0];
dayCount1 += countLeapYearDays(date1);
long int dayCount2 = (date2[2] * 365);
dayCount2 += monthDays[date2[1]];
dayCount2 += date2[0];
dayCount2 += countLeapYearDays(date2);
return (abs(dayCount1 - dayCount2));
}
int main(){
int date1[3] = {13, 3, 2021};
int date2[3] = {24, 5, 2023};
cout << "The number of days between two dates is " << countNoOfDays(date1, date2);
return 0;
}
আউটপুট
The number of days between two dates is 802
দ্রষ্টব্য: প্রদত্ত কোডটি এন্ডলেস পয়েন্টের সমস্যার সমাধান না করে বরং দুটি তারিখের মধ্যবর্তী দিনের সংখ্যা বের করার সমস্যা সমাধান করেছে। এন্ডলেস পয়েন্টের সঠিক সমাধান নিচে দেওয়া হলো:
সঠিক প্রোগ্রাম উদাহরণ (এন্ডলেস পয়েন্টের জন্য)
#include <bits/stdc++.h>
using namespace std;
#define MAX 100
int countEndlessPoints(bool mat[][MAX], int n, int m) {
// DP টেবিল: rowEndless[i][j] = mat[i][j] থেকে নিচে সব ১ কিনা
// colEndless[i][j] = mat[i][j] থেকে ডানে সব ১ কিনা
bool rowEndless[MAX][MAX] = {false};
bool colEndless[MAX][MAX] = {false};
// শেষ সারি ও কলাম ইনিশিয়ালাইজ
for (int j = 0; j < m; j++)
rowEndless[n-1][j] = mat[n-1][j];
for (int i = 0; i < n; i++)
colEndless[i][m-1] = mat[i][m-1];
// নিচ থেকে উপরে DP ফিল
for (int i = n-2; i >= 0; i--)
for (int j = 0; j < m; j++)
rowEndless[i][j] = mat[i][j] && rowEndless[i+1][j];
// ডান থেকে বামে DP ফিল
for (int j = m-2; j >= 0; j--)
for (int i = 0; i < n; i++)
colEndless[i][j] = mat[i][j] && colEndless[i][j+1];
// এন্ডলেস পয়েন্ট কাউন্ট
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (rowEndless[i][j] && colEndless[i][j])
count++;
return count;
}
int main() {
bool mat[MAX][MAX] = {
{0, 0},
{1, 1}
};
int n = 2, m = 2;
cout << "Number of endless points: " << countEndlessPoints(mat, n, m);
return 0;
}
আউটপুট
Number of endless points: 2
