Login/RegisterProgram Discussion :: Array
89 / 30
Explain Rat in a Maze problem. What data structure you will use. Can you Write code for it.
Answer:
#include
#include
#define N 4
using namespace std;
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout
Asked In ::
Language:
Vishal Rai
7 Jul, 2017 9:30 AM
#include<stdio.h>
#define N 4
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", sol[i][j]);
printf("\n");
}
}
bool isSafe(int maze[N][N], int x, int y)
{
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
else
return false;
}
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if(solveMazeUtil(maze, 0, 0, sol) == false)
{
printf("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}
if(isSafe(maze, x, y) == true)
{
sol[x][y] = 1;
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;
sol[x][y] = 0;
return false;
}
return false;
}
// driver program to test above function
int main()
{
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
solveMaze(maze);
return 0;
}
Language:
Vignesh
7 Jul, 2017 9:30 AM
#include <iostream>
#include<stdio.h>
#define N 4
using namespace std;
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout<<sol[i][j];
cout<<"\n";
}
}
bool isSafe(int maze[N][N], int x, int y)
{
if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
return true;
else
return false;
}
bool solveMaze(int maze[N][N])
{
int sol[N][N] = { {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if(solveMazeUtil(maze, 0, 0, sol) == false)
{
cout<<"Solution doesn't exist";
return false;
}
printSolution(sol);
return true;
}
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}
if(isSafe(maze, x, y) == true)
{
sol[x][y] = 1;
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;
sol[x][y] = 0;
return false;
}
return false;
}
/* driver program to test above function*/
int main()
{
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
solveMaze(maze);
return 0;
}
