Data-Structures-and-Algorithms/Algorithms/BackTracking/find-shortest-path-in-maze.cpp at master · Manvityagi/Data-Structures-and-Algorithms · 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
#include <bits/stdc++.h>
using namespace std;
int M = 10, N = 10;
int minpath = INT_MAX;

int row[] = {0, 0, 1, -1};
int col[] = {1, -1, 0, 0};

bool isValid(int r, int c)
{
    return r >= 0 && r < M && c >= 0 && c < N;
}

int mat[10][10] =
    {
        {1, 1, 1, 1, 1, 0, 0, 1, 1, 1},
        {0, 1, 1, 1, 1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 1, 1, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
        {0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 1, 1, 1, 0, 0, 1, 1, 0},
        {0, 0, 0, 0, 1, 0, 0, 1, 0, 1},
        {0, 1, 1, 1, 1, 1, 1, 1, 0, 0},
        {1, 1, 1, 1, 1, 0, 0, 1, 1, 1},
        {0, 0, 1, 0, 0, 1, 1, 0, 0, 1},
};

vector<vector<bool>> visited(M, vector<bool>(N, false));

void mazepath(int destx, int desty, int currx, int curry, int currlen)
{
    visited[currx][curry] = true;
    if (currx == destx && curry == desty)
    {
        //update ans if needed
        if (currlen < minpath)
        {
            minpath = currlen;
        }
        visited[currx][curry] = false;
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        int newx = currx + row[i];
        int newy = curry + col[i];

        if (mat[newx][newy] == 1 && isValid(newx, newy) && !(visited[newx][newy]))
        {
            mazepath(destx, desty, newx, newy, currlen + 1);
            visited[newx][newy] = false;
        }
    }
}

int main()
{
    int srcx, srcy;
    int destx, desty;
    cin >> srcx >> srcy >> destx >> desty;

    mazepath(destx, desty, srcx, srcy, 0);

    cout << minpath;
}