এই সমস্যাতে, আমাদের একটি 2 x n আকারের আয়তাকার গ্রিড দেওয়া আছে। আমাদের কাজ হল C++-এ এমন একটি প্রোগ্রাম তৈরি করা যাতে গ্রিডে আঁচবিক (vertically, horizontally বা diagonally) কোনো দুটি উপাদান নেওয়া না হয় এমন শর্তে সর্বোচ্চ যোগফল বের করা যায়।
সমস্যার বিবরণ
সর্বোচ্চ যোগফল বের করতে হলে, বর্তমান উপাদানের সাথে আঁচবিক কোনো উপাদান (ভertetically, horizontally বা diagonally) নেওয়া যাবে না।
উদাহরণ
ইনপুট
rectGrid[2][] = {{3, 8, 9}, {4, 1, 1}}
আউটপুট
13
ব্যাখ্যা
সম্ভব সব যোগফলগুলো:
- rectGrid[0][0] অর্থাৎ 3 থেকে শুরু করলে, শুধু 9 বা 1 যোগ করা যায়। সর্বোচ্চ যোগফল = 12।
- rectGrid[1][0] অর্থাৎ 4 থেকে শুরু করলে, শুধু 9 বা 1 যোগ করা যায়। সর্বোচ্চ যোগফল = 13।
- rectGrid[0][1] অর্থাৎ 8 থেকে শুরু করলে, আর কোনো উপাদান যোগ করা যায় না। সর্বোচ্চ যোগফল = 8।
- rectGrid[1][1] অর্থাৎ 1 থেকে শুরু করলে, আর কোনো উপাদান যোগ করা যায় না। সর্বোচ্চ যোগফল = 1।
- rectGrid[0][2] অর্থাৎ 9 থেকে শুরু করলে, শুধু 3 বা 4 যোগ করা যায়। সর্বোচ্চ যোগফল = 13।
- rectGrid[1][2] অর্থাৎ 1 থেকে শুরু করলে, শুধু 3 বা 4 যোগ করা যায়। সর্বোচ্চ যোগফল = 5।
সামগ্রিক সর্বোচ্চ যোগফল হল 13।
সমাধানের পদ্ধতি
এই সমস্যা 이전에 আলোচনা করা "আঁচবিক উপাদান ছাড়া সর্বোচ্চ যোগফল" সমস্যার সাথে মিলتی জুলটি। পার্থক্য হল এখানে অ্যারে 2D এবং আঁচবিক উপাদানের শর্ত ভিন্ন। প্রতিটি কলামে দুটি সারি থাকায়, আমরা বاری বاری উপাদান নেওয়ার সর্বোচ্চ সম্ভাবনা বিবেচনা করব।
প্রোগ্রাম উদাহরণ
#include <iostream>
using namespace std;
int findMax(int a, int b) {
if (a > b)
return a;
return b;
}
int calcMaxSum(int rectGrid[2][20], int N) {
int currectSum = 0;
int nextSum = 0;
int altSum;
for (int i = 0; i < N; i++) {
altSum = findMax(nextSum, currectSum);
currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
nextSum = altSum;
}
int maxSum = findMax(nextSum, currectSum);
return maxSum;
}
int main() {
int rectGrid[2][20] = {{3, 8, 9, 5},
{4, 1, 2, 7}};
int N = 4;
cout << "The maximum sum in a 2 x " << N << " grid such that no two elements are adjacent is " << calcMaxSum(rectGrid, N);
return 0;
}
আউটপুট
The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15
