Ronzii's Blog

Just your average geek's blog

Rat in a Maze Problem

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 4
using namespace std;
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");
    }
}
int isSafe(int maze[N][N],int x, int y)
{
    if(x>=0 & x<N && y>=0 && y<N && maze[x][y]==1)
    {
        return 1;
    }
    return 0;
}
int solveProblem(int x, int y,int sol[N][N],int maze[N][N])
{
    if(x==N-1 && y==N-1)
    {
        sol[x][y] = 1;
        printSolution(sol);
        return 1;
    }
    else if(isSafe(maze,x,y))
    {
        sol[x][y] = 1;
        if(solveProblem(x+1,y,sol,maze))
        {
            return 1;
        }
        if(solveProblem(x,y+1,sol,maze))
        {
            return 1;
        }
        sol[x][y] = 0;
    }
    return 0;
}
void solveMaze(int maze[N][N])
{
    int sol[N][N];
    memset(sol, 0, sizeof sol);
    solveProblem(0,0,sol,maze);
}
int main()
{
    int maze[N][N]  =
    {
        {1, 1, 1, 1},
        {0, 1, 0, 0},
        {0, 1, 1, 1},
        {0, 1, 0, 1}
    };
    solveMaze(maze);
    return 0;
}
Advertisements

July 21, 2011 - Posted by | C++ | , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s