can anybody help me with this project , hints : Here\'s the sample output Matrix

Question

can anybody help me with this project ,

hints :

Here's the sample output

Matrix Representation of Sample Maze 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 O 1 1 1 1 O O 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 The rat-in-a-maze problem is to find a path from the entrance to the exit of the maze. A path is a sequence of positions, none of which is blocked, such that each (other than the first)is the north, south, east or west neighbor of the preceding position. You are to write a program to solve the rat-in-a-maze problem. You may assume that the mazes for which your program is to work are sufficiently small so that the entire maze can be represented in the memory of the target computer. Your program will be read in command line parameters containing filenames of maxes to process The first line of the maze file will be ROW COUNT COLUMN COUNT proceeding lines with be a matrix of 1's and 0's depending on if it is blocked or not. See one of the provided maze text files. You can assume that the input files have correct syntax. The command line arguments will be received as follows: mazefilel mazefile2 maZefilen If more then one file argument is provided, your program will process multiple mazes during a single execution.

Explanation / Answer

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<stack>
using namespace std;
struct point{
int x;
int y;
};
stack<struct point> res ;
struct point p;
bool solveMazeUtil(int** maze, int x, int y, int** sol, int row, int col, string direction);

/* A utility function to print solution matrix sol[N][N] */
void printSolution(int** sol, int row, int col)
{
cout<<"Path : ";
//cout<<"size of result is "<<res.size()<<endl;
// while(res.empty()!=true){
// struct point t=res.top();
// res.pop();
// cout<<t.x<<" "<<t.y<<endl;
// }
  
for (int i = row; i > 0 ; i--)
{
for (int j = col; j > 0 ; j--){
if(sol[i-1][j-1] == 0)
continue;
if(i==row && j==col)
cout<<"("<<i<<", "<<j<<") ";
else
cout<<"<- ("<<i<<", "<<j<<") ";
}
}
}

/* A utility function to check if x,y is valid index for row*col maze */
bool isSafe(int** maze, int x, int y, int row, int col)
{
// if (x,y outside maze) return false
if(x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == 0)
return true;

return false;
}

/* This function solves the Maze problem using Backtracking. It mainly
uses solveMazeUtil() to solve the problem. It returns false if no
path is possible, otherwise return true and prints the path in the
form of 1s. Please note that there may be more than one solutions,
this function prints one of the feasible solutions.*/
bool solveMaze(int** maze, int row, int col)
{
int** sol = (int**)malloc(sizeof(int*)*row);
for(int i = 0 ; i < row ; i++)
{
sol[i] = (int*)malloc(sizeof(int)*col);
for(int j = 0 ; j < col ; j++)
{
sol[i][j] = 0;
}
}

if(solveMazeUtil(maze, 0, 0, sol, row, col, "down") == false)
{
printf("No Path Found !");
return false;
}

printSolution(sol, row, col);
return true;
}

/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int** maze, int x, int y, int** sol, int row, int col, string direction)
{
// if (x,y is goal) return true
if(x == row-1 && y == col-1)
{
p.x = x+1;
p.y = y+1;
res.push(p);
sol[x][y] = 1;
return true;
}

// Check if maze[x][y] is valid
if(isSafe(maze, x, y, row, col) == true)
{
// mark x,y as part of solution path
p.x = x+1;
p.y = y+1;
res.push(p);
sol[x][y] = 1;

// now rat has four options, either go right OR go down or left or go up
if(direction!="up" && solveMazeUtil(maze, x+1, y, sol, row, col, "down"))
{ //go down
           p.x = x+1;
p.y = y+1;
res.push(p);
return true;
       }
       //else go down
       if(direction!="left" && solveMazeUtil(maze, x, y+1, sol, row, col, "right"))
       { //go right
           p.x = x+1;
p.y = y+1;
res.push(p);
return true;
       }
       if(direction!="down" && solveMazeUtil(maze, x-1, y, sol, row, col, "up"))
       { //go up
           p.x = x+1;
p.y = y+1;
res.push(p);
return true;
       }
       if(direction!="right" && solveMazeUtil(maze, x, y-1, sol, row, col, "left"))
       { //go left
           p.x = x+1;
p.y = y+1;
res.push(p);
return true;
       }

/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
sol[x][y] = 0;
res.pop();
return false;
}   
res.pop();
return false;
}

// driver program to test above function
int main()
{
int row, col;
cin>>row;
cin>>col;
int** maze = (int**)malloc(sizeof(int*)*row);
  
for(int i = 0 ; i < row ; i++)
{
maze[i] = (int*)malloc(sizeof(int)*col);
for(int j = 0 ; j < col ; j++)
{
cin>>maze[i][j];
}
}
solveMaze(maze, row, col);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.