C++ প্রোগ্রামে র্যাট ইন এ মেজ (Rat in a Maze) - ব্যাকট্র্যাকিং

ভূমিকা

একটি ২D মেজ (maze) দেওয়া আছে যেখানে কিছু সেল ব্লকড (১) এবং কিছু খালি (০)। সোর্স (০,০) থেকে ডেস্টিনেশন (N-1,N-1) পর্যন্ত পাথ বের করতে হবে ব্যাকট্র্যাকিং (backtracking) ব্যবহার করে।

উদাহরণ

ইনপুট মেজ (৫x৫):
0 1 0 1 1
0 0 0 0 0
1 0 1 0 1
0 0 1 0 0
1 0 0 1 0

আউটপুট (পাথ):
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

C++ প্রোগ্রাম উদাহরণ

#include 
using namespace std;
#define SIZE 5

int maze[SIZE][SIZE] = {
    {0,1,0,1,1}, {0,0,0,0,0}, {1,0,1,0,1},
    {0,0,1,0,0}, {1,0,0,1,0}
};
int sol[SIZE][SIZE] = {0};

void printSolution() {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) cout << sol[i][j] << "\t";
        cout << "\n\n";
    }
}

int solveMaze(int r, int c) {
    if (r == SIZE-1 && c == SIZE-1) { sol[r][c] = 1; return 1; }
    if (r>=0 && c>=0 && r

আউটপুট
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1