C प्रोग्राम में भूलभुलैया में चूहा - बैकट्रैकिंग

समस्या विवरण

भूलभुलैया में चूहा बैकट्रैकिंग का उपयोग करने वाली एक लोकप्रिय समस्या है।

एक भूलभुलैया 2D मैट्रिक्स है जिसमें कुछ सेल अवरुद्ध हैं। उनमें से एक सेल स्रोत सेल है, जहां से हमें शुरू करना है। और दूसरा गंतव्य है, जहां हमें पहुंचना है। हमें किसी भी अवरुद्ध सेल में जाए बिना स्रोत से गंतव्य तक एक पथ ढूंढना है।

उदाहरण

इनपुट: maze[][] = { {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 <iostream>
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 solution[SIZE][SIZE];

void printsolution() {
    for(int i = 0; i < SIZE; i++) {
        for(int j = 0; j < SIZE; j++) {
            printf("%d\t", solution[i][j]);
        }
        printf("\n\n");
    }
}

int solvemaze(int r, int c) {
    if((r == SIZE-1) && (c == SIZE-1)) {
        solution[r][c] = 1;
        return 1;
    }
    if(r >= 0 && c >= 0 && r < SIZE && c < SIZE && solution[r][c] == 0 && maze[r][c] == 0){
        solution[r][c] = 1;
        if(solvemaze(r+1, c)) return 1;
        if(solvemaze(r, c+1)) return 1;
        if(solvemaze(r-1, c)) return 1;
        if(solvemaze(r, c-1)) return 1;
        solution[r][c] = 0;
        return 0;
    }
    return 0;
}

int main() {
    for(int i = 0; i < SIZE; i++)
        for(int j = 0; j < SIZE; j++)
            solution[i][j] = 0;
    if (solvemaze(0,0))
        printsolution();
    else
        printf("कोई समाधान नहीं\n");
    return 0;
}