ডাইমেনশন সারি X col সহ একটি 2D ম্যাট্রিক্স দেওয়া হয়েছে৷ লক্ষ্য হল ম্যাট্রিক্সকে 0,0 থেকে সেল সারি, col শুধুমাত্র ডান এবং নিচের মুভ ব্যবহার করে ম্যাট্রিক্স অতিক্রম করতে পারে এমন সংখ্যা গণনা করা, অর্থাৎ প্রথম পদক্ষেপটি 0,0 থেকে 0,1 (নিচে) বা 1,0 হতে পারে। (ডান) এবং 1,1 (তির্যক) নয়।
উদাহরণস্বরূপ
ইনপুট
col = 2; row = 4
আউটপুট
Count of number of ways to traverse a Matrix are: 4
ব্যাখ্যা
যে উপায়ে আমরা সেল 0,0 থেকে 2,4 পর্যন্ত পৌঁছতে পারি তা দেখানো হয়েছে −
ইনপুট
col = 4; row = 3
আউটপুট
Count of number of ways to traverse a Matrix are: 10
ব্যাখ্যা
We will reduce the problem into smaller recursions. Count ways for col=3, row=2, then for col=2, row=1 ….. For col=1 or row=1 the answer will be 1. (only right or only down move).
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা একটি পুনরাবৃত্তি পদ্ধতি ব্যবহার করব। শেষে সারি বা কলের জন্য 1 হিসাবে। শুধুমাত্র একটি উপায় আছে যা হল 1টি সোজা ডান মুভ বা 1টি সোজা নিচের দিকে। এটি পুনরাবৃত্তির জন্য সমাপ্ত শর্ত হবে৷
৷-
ম্যাট্রিক্সের মাত্রার জন্য পূর্ণসংখ্যার সারি, কল নিন।
-
ফাংশন ways_traverse_matrix(int row, int col) মাত্রা নেয় এবং একটি ম্যাট্রিক্স অতিক্রম করার উপায়গুলির সংখ্যা প্রদান করে।
-
সারির জন্য==1, 1 রিটার্ন করুন।
-
col==1 এর জন্য, 1 রিটার্ন করুন।
-
অন্যথায় recursion ways_traverse_matrix(temp_1, col) +ways_traverse_matrix(সারি, temp_2) ব্যবহার করে উপায় গণনা করুন।
-
এখানে temp_1=আগের সারি নম্বর এবং temp_2=পূর্ববর্তী কলাম নম্বর।
-
শেষে আমরা মোট উপায়ের একটি গণনা পাব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int ways_traverse_matrix(int row, int col){
if (row == 1){
return 1;
}
else if(col == 1){
return 1;
} else {
int temp_1 = row − 1;
int temp_2 = col − 1;
return ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2);
}
}
int main(){
int col = 2;
int row = 2;
cout<<"Count the number of ways to traverse a Matrix are: "<<ways_traverse_matrix(row, col);
return 0;
} আউটপুট
যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেCount the number of ways to traverse a Matrix are: 2
