মেজে গন্তব্যে পৌঁছানোর পথের সংখ্যা গণনা (C++)

একটি মেজ row x col ম্যাট্রিক্স হিসেবে দেওয়া আছে যেখানে বাধা -1 এবং খালি সেল অন্য যেকোনো মান। লক্ষ্য হল প্রথম সেল arr[0][0]-থেকে শেষ সেল arr[row][col]-এ পৌঁছানোর পথের সংখ্যা বের করা যাতে শুধু দুটি মুভ অনুমোদিত:

• রাইট মুভ: arr[i][j] থেকে arr[i][j+1]
• ডাউন মুভ: arr[i][j] থেকে arr[i+1][j]

উদাহরণ দিয়ে বোঝা যাক

ইনপুট - arr[3][3] = {{0,0,0}, {-1,-1,0}, {0,0,0}}

আউটপুট - মেজে গন্তব্যে পৌঁছানোর পথের সংখ্যা: ১

ব্যাখ্যা

পথ: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

ইনপুট - arr[4][4] = {{0,0,0,0}, {-1,0,-1,0}, {-1,0,-1,0}, {0,0,0,0}}

আউটপুট - মেজে গন্তব্যে পৌঁছানোর পথের সংখ্যা: ২

ব্যাখ্যা - দুটি সম্ভাব্য পথ রয়েছে।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

প্রথমে সব ০ কে ১ করে দিন। আবার ম্যাট্রিক্স ট্রাভার্স করে প্রতিটি সেলের জন্য: যদি বাধা (-1) হয় তবে উপেক্ষা করুন। নয় তবে উপরের সেল (i-1,j) এবং বামের সেল (i,j-1) চেক করুন। যদি যেকোনো একটের মান ০-র চেয়ে বড় হয় তবে তার মান বর্তমান সেল (i,j)-এ যোগ করুন। এইভাবে (row-1,col-1)-এ মোট পথের সংখ্যা পাওয়া যাবে।

• ইনপুট অ্যারে arr[row][col] মেজ হিসেবে নিন।
• ফাংশন destination_maze(int arr[row][col]) ফলাফল রিটার্ন করে।
• যদি প্রথম সেল ব্লকড হয় তবে ০ রিটার্ন করুন।
• বাম কলাম ট্রাভার্স করে ০ গুলো ১ করুন। প্রথম বাধা পাওয়া গেলে ব্রেক।
• প্রথম রো ট্রাভার্স করে ০ গুলো ১ করুন। প্রথম বাধা পাওয়া গেলে ব্রেক।
• সেল (1,1) থেকে আবার ট্রাভার্স: যদি -1 হয় তবে কন্টিনিউ।
• যদি arr[i-1][j] > 0 বা arr[i][j-1] > 0 হয় তবে তাদের মান যোগ করুন।
• শেষে arr[row-1][col-1] > 0 হলে সেটি রিটার্ন করুন, অন্যথায় ০।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;
#define row 3
#define col 3

int destination_maze(int arr[row][col]) {
    if (arr[0][0] == -1) return 0;
    for (int i = 0; i < row; i++) {
        if (arr[i][0] == 0) arr[i][0] = 1;
        else break;
    }
    for (int i = 1; i < col; i++) {
        if (arr[0][i] == 0) arr[0][i] = 1;
        else break;
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (arr[i][j] == -1) continue;
            if (arr[i-1][j] > 0) arr[i][j] += arr[i-1][j];
            if (arr[i][j-1] > 0) arr[i][j] += arr[i][j-1];
        }
    }
    if (arr[row-1][col-1] > 0) return arr[row-1][col-1];
    else return 0;
}

int main() {
    int arr[row][col] = {
        {0, 0, 0},
        {-1, -1, 0},
        {0, 0, 0}
    };
    cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr);
    return 0;
}

উপরের কোড রান করলে নিচের আউটপুটটি পাওয়া যাবে:

আউটপুট

Count of number of ways to reach destination in a Maze are: 1