forked from Jithendra-Bathala236/team_09_cpp_100_programs
-
Notifications
You must be signed in to change notification settings - Fork 0
/
076ShortestPathInMaze.cpp
122 lines (104 loc) · 3.12 KB
/
076ShortestPathInMaze.cpp
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//program to find shortest path in a maze
// including required header files
#include <iostream>
using namespace std;
// Maximum maze size
const int MAX_N = 100;
int maze[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
// Possible moves: right, left, down, up
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
// Maze dimensions
int N, M;
// Checking weather the movement of block is valid or not
bool isValid(int x, int y)
{
return x >= 0 && x < N && y >= 0 && y < M && maze[x][y] == 1 && !visited[x][y];
}
// function to find the shortest path between start and end point
int shortestDistance(int startX, int startY, int endX, int endY)
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
visited[i][j] = false;
dist[i][j] = -1;
}
}
visited[startX][startY] = true;
dist[startX][startY] = 0;
bool found = false;
while (!found)
{
found = true;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (visited[i][j])
{
for (int k = 0; k < 4; k++)
{
int newX = i + dx[k];
int newY = j + dy[k];
if (isValid(newX, newY) && (dist[newX][newY] == -1 || dist[newX][newY] > dist[i][j] + 1))
{
dist[newX][newY] = dist[i][j] + 1;
visited[newX][newY] = true;
found = false;
}
if (newX == endX && newY == endY)
{
return dist[endX][endY];
}
}
}
}
}
}
// No path found
return -1;
}
// main function
int main()
{
// Input maze dimensions
cout << "Enter the number of rows in the maze: ";
cin >> N;
cout << "Enter the number of columns in the maze: ";
cin >> M;
// Input maze
cout << "Enter the values of the maze (1. movable blocks, 2. non movable blocks)" << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << "Enter the " << i + 1 << "th row " << j + 1 << "the column element in maze: ";
cin >> maze[i][j];
}
}
// Input start and end points
int startX, startY, endX, endY;
cout << "Enter the X-coordinate of starting position: ";
cin >> startX;
cout << "Enter the Y-coordinate of starting position: ";
cin >> startY;
cout << "Enter the X-coordinate of ending position: ";
cin >> endX;
cout << "Enter the Y-coordinate of ending position: ";
cin >> endY;
int shortestDist = shortestDistance(startX, startY, endX, endY);
// displaying result
if (shortestDist == -1)
{
cout << "No path found!" << endl;
}
else
{
cout << "Shortest distance in the maze from (" << startX << ", " << startY << ") to (" << endX << ", " << endY << ") is: " << shortestDist << endl;
}
return 0;
}