Ant in a Maze problem

-
Ant in a maze is another problem that can be solved using backtracking algorithm.In this problem there is a NxN  maze in which one corner of maze is entry point and other is exit point.Now there is an ant in a maze who wants to go from entry to exit.For doing this there are certain constraints like an ant can move only forward or downward but no backward and upward.For the sake of simplicity we are taking 4x4 Maze.The maze can be denoted by a matrix with values 0 and 1.0 means the path is blocked and 1 means the path is available.The maze and the path for ant from entry to exit is


The block which are in grey color are dead end in the maze that is the ant cannot go through such blocks.The red path is the path travelled by ant from entry to exit.The matrix representation of the above maze without the path will be (input to be taken)

maze[4][4]={{1,1,0,0},
{1,1,0,1},
{0,1,0,0},
{1,1,1,1}
}

and the matrix representation of path travelled by ant will be (output to be displayed)

Path[4][4]={{1,1,0,0},
{0,1,0,0},
{0,1,0,0},
{0,1,1,1}
}

Algorithm :

1) Mark current block in a matrix as 1
2) Move horizontally in forward direction and recursively check whether this leads to solution.
3) If the above step doesn't lead to the valid solution then move downwards and check whether this leads to the solution.
4) If none of the above solutions work then unmark the block as 0 and return false.

Program :

#include<stdio.h>
#include<conio.h>


bool Findpath(int maze[4][4], int x, int y, int Path[4][4])
{
    
    if(x == 3 && y == 3)           //Exit point is reached
    {
        Path[x][y] = 1;
        return true;
    }

   
    if(isvalid(maze, x, y) == true)     // Check if maze[x][y] is valid
    {
        
        Path[x][y] = 1;                        // mark x,y as part of solution

        
        if (Findpath(maze, x+1, y, Path) == true)     // Move forward in x direction
            return true;

        
           
        if (Findpath(maze, x, y+1, Path) == true)     // If moving in x direction doesn't give solution Move down 
            return true;

         
            
        Path[x][y] = 0;     // If the above steps didn't work then Backtrack that is unmark x,y as part of solution
        return false;
    }   
 printpath(Path);
    return false;
}


bool isvalid(int maze[4][4], int x, int y)
{
   
    if(x >= 0 && x < 4 && y >= 0 && y < 4)             // if x,y is inside maze then return true
{  
   if(maze[x][y]==1)
        return true;
 }
    return false;
}

void printpath(int Path[4][4])
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
            printf(" %d ", Path[i][j]);
        printf("\n");
    }
}

int main()
{
    int maze[4][4]  =  { {1, 1, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };


    int Path[4][4] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };
    bool a=Findpath(maze,0,0,Path);
   if(a==false)
{
 printf("Solution doesnot Exist\n");
return false;
}
    getch();
}


Comments

Post a Comment

Popular posts from this blog

Tricky Questions or Puzzles in C

-
This post is about the Tricky Questions   or code snippet in C or C++ asked in most of the Interviews   (See Interview Experience ) by some of the good companies. You may know probably the right concept but it will not strike you at the interview and to crack all those Interview Questions  you should know some of them beforehand. If you are applying for Job related to JAVA then checkout the blog post  Tricky Questions in JAVA . 1) what will be the output of the following Printf function.   printf("%d",printf("%d",printf("%d",printf("%s","ILOVECPROGRAM")))); Ans-ILOVECPROGRAM1321 The above printf line gives output like this because printf returns the number of character successfully written in the output. So the inner printf("%s","ILOVECPROGRAM") writes 13 characters to the output so the outer printf function will print 13 and as 13 is of 2 characters so the next outer printf function will print 2 and then
Read more

Program to uncompress a string ie a2b3c4 to aabbbcccc

-
Below is the program to uncompress a string #include<stdio.h> #include<conio.h> #include<stdlib.h> int main() { char str[100]="a2b3c4d8u7"; for(int i=0;str[i]!='\0';i++) { if(i%2!=0) { for(int j=0;j<atoi(&str[i]);j++) { printf("%c",str[i-1]); } } } getch(); } Want to become a Data Engineer? Check out below blog posts  1.  5 Key Skills Every Data Engineer needs in 2023 2.  How to prepare for Data Engineering Interviews 3.  Top 25 Data Engineer Questions
Read more

Number series arrangement puzzles

-
In this post I am going to give the number series arrangement puzzles in which you have to find the next element or missing element in the series of numbers given. These questions are an important part of any technical interviews where interviewer wants to check how fast you can think and deduce connections between numbers. 1. What is the next number in the series? 27  101  91 82 18 17 __ 2. What is the next number in the series? 83  99   1027    1181    12243  __ 3. What is the missing number in the series? 132   3134    5236    7338   __   115312 4. What is the missing numbers in the series? 31 34 __ 37 37 __ 40 40 40 __ 40 40 40 5. What is the next number in the series? 58   1024   2040    4056   __ Click  here  for answers
Read more