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.





Think With Ink

Differ your Content by Color.




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.

Answer:

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

Post Your Answer Here:

Name *
Email

Language:

Post Your Reply Here:



Language:

Post Your Reply Here: