algorithms-in-C-Cplusplus-Java-Python-JavaScript/rat_in_a_maze.cpp at master · imrishabhbansal/algorithms-in-C-Cplusplus-Java-Python-JavaScript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define n 4
using namespace std;

int sol[n][n]= {{0,0,0,0},
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0,}};

void print(int sol[n][n]);

int issafe(int maze[n][n], int row, int col)
{
    if(row>=0 && row<n && col>=0 && col<n && maze[row][col]==1)
            return 1;
    return 0;
}

int solvemaze(int maze[n][n], int row, int col, int sol[n][n])
{
    if(row==n-1 && col==n-1)
    {
        sol[row][col]=1;

        return 1;
    }

    if(issafe(maze,row,col) == 1)
    {

        sol[row][col]=1;
        print(sol);

        if(solvemaze(maze, row, col+1,sol) == 1)
        {
            return 1;
        }
        if(solvemaze(maze, row+1, col,sol) == 1)
        {
            return 1;
        }
        else
        {
            cout<<"Backtracking step \n";
            print(sol);
            sol[row][col]=0;
            return 0;
        }
    }
    return 0;
}


void print(int sol[n][n])
{
    int i,j;

    for(i=0;i<n;i++)
    {
        cout<<"|";
        for(j=0;j<n;j++)
        {
            cout<<" "<<sol[i][j]<<" |";
        }
        cout<<"\n";
    }
    cout<<"\n\n";
}
int main()
{

    /*int maze[n][n]={{1,1,1,0,0,1,1,1},
                    {0,0,1,1,0,0,0,0},
                    {0,0,1,0,0,0,0,0},
                    {0,1,1,1,0,0,0,0},
                    {0,0,0,1,0,0,0,0},
                    {0,0,0,1,0,1,1,1},
                    {0,0,0,1,0,1,0,1},
                    {0,0,0,1,1,1,0,1}};


    int sol[n][n] ={{0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0},
                    {0,0,0,0,0,0,0,0}};*/

        int maze[n][n]={{1,1,1,0},
                        {0,1,0,1},
                        {0,1,1,0},
                        {0,1,1,1}};


    cout<<"Maze"<<"\n";
    print(maze);

    solvemaze(maze,0,0,sol);


    print(sol);

}