একটি স্কয়ার ম্যাট্রিক্স matrix[][] নন-নেগেটিভ নম্বর ধারণ করে। একটি ভেরিয়েবল score দেওয়া আছে। লক্ষ্য হল matrix[0][0]-থেকে শুধু রাইট এবং ডাউন মুভ দিয়ে এলিমেন্ট যোগ করে দেওয়া score পৌঁছানোর পথের সংখ্যা বের করা।
উদাহরণ দিয়ে বোঝা যাক
উদাহরণ ১
ইনপুট - matrix[2][2] = {{1,1}, {1,1}}, score=3
আউটপুট - নির্দিষ্ট স্কোর পৌঁছানোর পথের সংখ্যা: ২
ব্যাখ্যা - দুটি পথ:
- (0,0)+(0,1)+(1,1) = 1+1+1=3
- (0,0)+(1,0)+(1,1) = 1+1+1=3
উদাহরণ ২
ইনপুট - matrix[3][3] = {{1,1,2}, {2,1,1}, {1,2,2}}, score=7
আউটপুট - নির্দিষ্ট স্কোর পৌঁছানোর পথের সংখ্যা: ২
ব্যাখ্যা - দুটি পথ:
- (0,0)+(0,1)+(1,1)+(1,2)+(2,2) = 1+1+1+2+2=7
- (0,0)+(0,1)+(1,1)+(2,1)+(2,2) = 1+1+1+2+2=7
প্রোগ্রামে ব্যবহৃত পদ্ধতি
ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমাধান। দুটি অ্যারে arr[row][col][size] এবং check[row][col][size]। check ভিজিটেড সেল মার্ক করে। arr[][][] নির্দিষ্ট সেলে পৌঁছানোর পথ সংখ্যা সংরক্ষণ করে। রিকার্সিভলি পথ সংখ্যা হিসাব করা হয়।
- ২ডি অ্যারে
matrixনম্বর সংরক্ষণের জন্য। - ভেরিয়েবল
scoreইনপুট নিন। - দুটি অ্যারে
int arr[row][col][size]এবংbool check[row][col][size]। - ফাংশন
matrix_score(int matrix[row][col], int rows, int cols, int sc)পথ সংখ্যা রিটার্ন করে। - যদি
sc < 0হয় তবে ০ রিটার্ন করুন। - যদি
- যদি
rows==0 && cols==0হয় তবেsc==matrix[0][0]হলে ১ রিটার্ন করুন, অন্যথায় ০। - যদি
check[rows][cols][sc]true হয় তবেarr[rows][cols][sc]রিটার্ন করুন। - অন্যথায়
check[rows][cols][sc]=true। temp_1 = matrix_score(matrix, rows-1, cols, sc-matrix[rows][cols])।temp_2 = matrix_score(matrix, rows, cols-1, sc-matrix[rows][cols])।arr[rows][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
