একটি বর্গ ম্যাট্রিক্স [][] দেওয়া হয়েছে যার উপাদান হিসাবে অ ঋণাত্মক সংখ্যা রয়েছে। এছাড়াও একটি পরিবর্তনশীল স্কোর দেওয়া. লক্ষ্য হল ম্যাট্রিক্স[][] থেকে উপাদানগুলি যোগ করে প্রদত্ত স্কোরে পৌঁছানোর উপায়গুলি গণনা করা যাতে কেবলমাত্র ডান চাল এবং নীচের চালগুলি অনুমোদিত হয়৷
ম্যাট্রিক্স[0][0] থেকে শুরু করে শুধুমাত্র মুভ হতে পারে, ম্যাট্রিক্সে [0][1] (ডান মুভ) বা ম্যাট্রিক্সে [1][0] (ডাউন মুভ) এ সরানো এবং যোগফল=স্কোরে পৌঁছানোর জন্য মান যোগ করা যেতে পারে।
আসুন উদাহরণ দিয়ে বোঝা যাক।
উদাহরণস্বরূপ
ইনপুট - ম্যাট্রিক্স[রো [কল] ={ {1, 1}, { 1, 1} } স্কোর=3
আউটপুট - একটি ম্যাট্রিক্সে একটি প্রদত্ত স্কোরে পৌঁছানোর উপায়গুলির সংখ্যা হল:2
ব্যাখ্যা - নিম্নলিখিত উপায়ে স্কোর পৌঁছানো যেতে পারে:
উপায় 1:সূচকে উপাদান যোগ করা (0,0) + (0,1) + (1,1) =1+1+1 =3
উপায় 2:সূচকে উপাদান যোগ করা (0,0) + (1,0) + (1,1) =1+1+1 =3
ইনপুট - ম্যাট্রিক্স[রো [কল] ={ {1,1,2},{ 2,1,1}, {1,2,2} } স্কোর=7
আউটপুট - একটি ম্যাট্রিক্সে একটি প্রদত্ত স্কোরে পৌঁছানোর উপায়গুলির সংখ্যা হল:2
ব্যাখ্যা - নিম্নলিখিত উপায়ে স্কোর পৌঁছানো যেতে পারে:
উপায় 1:সূচকে উপাদান যোগ করা (0,0) + (0,1) + (1,1) + (1,2) + (2,2) =1+1+1+2+2 =7
উপায় 2:সূচকে উপাদান যোগ করা (0,0) + (0,1) + (1,1) + (2,1) + (2,2) =1+1+1+2+2 =7
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা সমস্যা সমাধানের জন্য ডায়নামিক প্রোগ্রামিং ব্যবহার করব। আমরা দুটি অ্যারে ব্যবহার করব arr[row][col][size] এবং check[row][col][size]। অ্যারে চেক ম্যাট্রিক্সের কোষগুলিকে চিহ্নিত করবে [][][] যদি সেগুলি সত্য হিসাবে পরিদর্শন করা হয়। অ্যারে arr[][][] ম্যাট্রিক্স[0][0] থেকে একটি নির্দিষ্ট ঘরে পৌঁছানোর উপায়গুলির সংখ্যা সংরক্ষণ করতে ব্যবহৃত হয়। পুনরাবৃত্তিমূলকভাবে আমরা উপায়গুলি গণনা করব।
- সংখ্যা সংরক্ষণের জন্য 2D অ্যারে ম্যাট্রিক্স নিন।
- ভেরিয়েবল স্কোরকে ইনপুট হিসেবে নিন।
- দুটি অ্যারে int arr[row][col][size] এবং bool check[row][col][size] নিন।
- ফাংশন matrix_score(int matrix[row][col], int rows, int cols, int sc) একটি ম্যাট্রিক্সে একটি প্রদত্ত স্কোরে পৌঁছানোর উপায়গুলির সংখ্যা ফেরত দিতে ব্যবহৃত হয়৷
- স্কোর sc 0 এর কম হলে 0 ফেরত দিন। ( পুনরাবৃত্তি শেষ করতে বা ভুল ইনপুটের ক্ষেত্রে)
- যদি সারি বা কলামের সংখ্যা 0 এর কম হয় তাহলে 0 ফেরত দিন। ( পুনরাবৃত্তি শেষ করতে)।
- যদি প্রথম ঘরটি sc (ইনপুট স্কোর) এর সমান হয় তাহলে একমাত্র উপায় হিসেবে 1 দিন। যদি তা না হয় তাহলে 0 ফেরত দিন।
- যদি বর্তমান কক্ষটি ইতিমধ্যেই পরিদর্শন করা হয়, তাহলে এই কক্ষে arr[rows][cols][sc] হিসাবে সংখ্যাটি ফেরত দিন।
- উপরের সমস্ত শর্ত না থাকলে বর্তমান সেলটিকে পরিদর্শন করা হিসাবে চিহ্নিত করুন। চেক[সারি][cols][sc] =সত্য। ব্যবহার করে
- গণনা করুন temp_1 =ম্যাট্রিক্স_স্কোর(ম্যাট্রিক্স, সারি-১, কল, এসসি-ম্যাট্রিক্স[সারি][কল])
- গণনা করুন temp_2 =ম্যাট্রিক্স_স্কোর(ম্যাট্রিক্স, সারি, কল-১, এসসি-ম্যাট্রিক্স[সারি][কল])
- অ্যার[সারি][cols][sc] =temp_1 + temp_2 হিসাবে উপায়ের সংখ্যা সেট করুন।
- শেষে arr[rows][cols][sc] ফেরত দিন।
উদাহরণ
#include <iostream>
using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];
int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
if (ways < 0) {
return 0;
}
if (rows < 0 || cols < 0) {
return 0;
}
if (rows == 0) {
if (cols == 0) {
if (ways == matrix[0][0]) {
return 1;
} else {
return 0;
}
}
}
if (check[rows][cols][ways]) {
return arr[rows][cols][ways];
}
check[rows][cols][ways] = true;
int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
arr[rows][cols][ways] = temp_1 + temp_2;
return arr[rows][cols][ways];
}
int main() {
int matrix[row][col] = {
{
1,
1
},
{
1,
1
}
};
int ways = 3;
cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
return 0;
} যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেআউটপুট
Count of number of ways to reach a given score in a Matrix are: 2
