Question

URGENT!!!!! I need to develop a C++ program that uses a recursive function to solve this maze problem: (No classes please!!!!) A robot is asked to navigate a maze. It is placed at a certain position (the starting position) in the maze and is asked to try to reach another position (the goal position). Positions in the maze will either be open or blocked with an obstacle. Positions are identified by (x,y) coordinates. At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are: Ø Go North: (x,y) -> (x,y-1) Ø Go East: (x,y) -> (x+1,y) Ø Go South: (x,y) -> (x,y+1) Ø Go West: (x,y) -> (x-1,y) Note that positions are specified in zero-based coordinates (i.e., 0...size-1, where size is the size of the maze in the corresponding dimension). The robot can only move to positions without obstacles and must stay within the maze. The robot should search for a path from the starting position to the goal position (a solution path) until it finds one or until it exhausts all possibilities. In addition, it should mark the path it finds (if any) in the maze. To make this problem more concrete, let's consider a maze represented by a matrix of characters. An example 6x6 input maze is: S##### .....# #.#### #.#### 'S' - start position (here, x=0, y=0) ...#.G 'G' - goal (here, x=5, y=4) A path in the maze can be marked by the '+' symbol... A path refers to either a partial path, marked while the robot is still searching: +##### ++++.# (i.e., one that may or may #.#### #.#### not lead to a solution). Or, ...#.G a solution path: ##...# S##### which ++...# #+#### leads from #+#### .++#+G ##+++# ##...# '.' - where the robot can move (open positions) '#' - obstacles (blocked positions)

Thank you, I will upvote your answer if it works and is correct

Answer 1

#include <iostream>
#include <vector>
using namespace std;

#define M 5 //Number of rows
#define N 6 //Number of columns

// Function to check if (i, j) is valid matrix coordinate
int flag = 0;
vector<pair<int,int> > path;
vector<vector<int> > vis(M,vector<int>(N,0));

bool isvalid(int i, int j,char mat[][N])
{
   return (i >= 0 && i < M && j >= 0 && j < N && vis[i][j]==0 && mat[i][j]!='#');
}

//// Function to print the route taken
//void printPath(vector<int> const &path, int last)
//{
//   for (int i : path)
//       cout << i << " - ";
//   cout << last << endl;
//}

void findPaths(char mat[][N], int i, int j)
{
   // if we have reached the last cell, print the route
   if (mat[i][j] == 'G')
   {  
       flag=1;
       return;
   }
  
   // include current cell in path
   vis[i][j]=1;
   path.push_back({i,j});  

   // move right
   if (isvalid(i, j + 1,mat))
       findPaths(mat, i, j + 1);
   if(flag)
       return;

   // move down
   if (isvalid(i + 1, j,mat))
       findPaths(mat,i + 1, j);
   if(flag)
       return;
      
   if (isvalid(i, j - 1,mat))
       findPaths(mat,i + 1, j);
   if(flag)
       return;
      
   if (isvalid(i - 1, j,mat))
       findPaths(mat,i + 1, j);
   if(flag)
       return;

   // remove current cell from the path
   path.pop_back();
   vis[i][j]=0;
}

// main function
int main()
{
  
  
  
   char mat[M][N];
   int sx,sy;
   cout<<"Enter the elements (seperated by space) : ";
   for(int i=0;i<M;i++){
       for(int j=0;j<N;j++){
           cin>>mat[i][j];
           if(mat[i][j]=='S'){
               sx=i;sy=j;
           }
       }
      
}

   findPaths(mat, sx, sy);
   if(flag==0)
       cout<<"No path found"<<endl;
   for(int i=0;i<path.size();i++){
       int x = path[i].first;
       int y = path[i].second;
       mat[x][y]='+';
   }
   mat[sx][sy]='S';
  
   for(int i=0;i<M;i++){
       for(int j=0;j<N;j++)
           cout<<mat[i][j]<<" ";
       cout<<endl;
   }

   return 0;
}

INPUT :

S # #

. # #

. . G

OUTPUT :

S # #

+ # #

+ + G

// IF NO PATH IS PRESENT OUTPUT IS : No path found

//If you got the answer, please upvote :)