Note 1
Take Note:

Take a note while surfing.

Note With Ink

Give your Note a Colorful Tag.

Easy to Access

Stay on same information and in Sync wherever you are.

Note 2
Take Note:

Organize your information,It may take Shape.

Easy to Access

Easy to pull up your content from anywhere anytime.

Note 3
Take Note:

Don't Let information to miss,Because it take shape

Note With Ink

Simple an Easy Way to take a note.

Easy to Access

Get the same in next visit.

Program Discussion :: Array
Home > Programs > Array

``89. Explain Rat in a Maze problem. What data structure you will use. Can you Write code for it.``

``````
#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;}
``````