I have got this maze of 2d matrix. '@' indicates the start and '#' indicates the end. 0 means the path is blocked and 1 means that you can pass through. The program needs to solve the maze and print the co-ordinates of each element in the path it found.
Example Input:
5 10
@ 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1
0 1 0 1 0 1 1 1 0 1
1 1 1 1 0 1 0 0 0 1
# 0 0 1 1 1 1 1 1 1
First line is the row and column of the matrix.
#include<bits/stdc++.h>
using namespace std;
void findPath(int i, int j, vector<vector<string>> &maze, vector<vector<string>> &visited, int endX, int endY, int maxRow, int maxCol){
if(i == endX && j == endY){
return;
}
cout << i << " " << j << endl;
visited[i][j] = "1";
if(maze[i][j + 1] == "1" && visited[i][j + 1] != "1" && j + 1 < maxCol){
findPath(i, j + 1, maze, visited, endX, endY, maxRow, maxCol);
}
if(maze[i + 1][j] == "1" && visited[i + 1][j] != "1" && i + 1 < maxRow){
findPath(i + 1, j, maze, visited, endX, endY, maxRow, maxCol);
}
if(maze[i][j - 1] == "1" && visited[i][j - 1] != "1" && j - 1 >= 0){
findPath(i, j - 1, maze, visited, endX, endY, maxRow, maxCol);
}
if(maze[i - 1][j] == "1" && visited[i - 1][j] != "1" && i - 1 >= 0){
findPath(i - 1, j, maze, visited, endX, endY, maxRow, maxCol);
}
visited[i][j] = "0";
}
int main()
{
freopen("input.txt", "r", stdin);
int row, col;
cin >> row >> col;
vector<vector<string>> maze(row, vector<string>(col));
vector<vector<string>> visited(row, vector<string>(col));
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
cin >> maze[i][j];
}
}
int startX, startY, endX, endY;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(maze[i][j] == "@"){
startX = i;
startY = j;
maze[i][j] = "1";
}
if(maze[i][j] == "#"){
endX = i;
endY = j;
maze[i][j] = "1";
}
}
}
findPath(startX, startY, maze, visited, endX, endY, row, col);
}
I made this code but it ends in segmentation fault and no output. It prints the co-ordinates for the initial row but then when it has to go down, it breaks.
My Output:
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
Is my approach wrong or have I missed something please help.
if(maze[i][j + 1] == "1" && visited[i][j + 1] != "1" && j + 1 < maxCol)
j + 1 < maxCol
is a correct check but it's too late. maze[i][j + 1]
and visited[i][j + 1]
have already been accessed. You need to do bounds checking before you access the arrays, not after. Same thing with all other if
statements.
if(j + 1 < maxCol && maze[i][j + 1] == "1" && visited[i][j + 1] != "1")