Maze Problem With Four Directional Movement(Left, Right, Up, Down)

Algo:-
1) Start with Position (x= 0, y=0)
2) If Reached the target,then Print the path.
3) Otherwise Check Below Condition
   3.1) Is it in boundary
   3.2) Is it valid(i.e maze[x][y] == 1)
   3.3) If Valid, then check Is it visited(i.e maze[x][y] == 2)
   4) Move Up(x-1,y)
   5) Move Right(x,y+1)
   6) Move Down(x+1,y)
   7) Move Left(x,y-1)

Code:-


 // if (x,y outside maze && path is not valid && visited) return false
bool isMazeSafe(int maze[M][N], int x, int y)
{

    if(x >= 0 && x < M && y >= 0 && y < N && maze[x][y] == 1 && maze[x][y] != 2)
    {
        /*Mark as visited, also can be done other way*/
         maze[x][y] = 2;
         return true;
    }

    return false;
}


/* A recursive function to solve mazeProblem */
int mazeProblemUtil(int maze[M][N], int x, int y, int sol[M][N])
{
    // Reached Target
    if(x == M-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }

    if(isMazeSafe(maze, x, y) == true)
    {
        // mark as it is valid
        sol[x][y] = 1;
     
        /* Move Up */
        if(x > 0)
        {
         if (mazeProblemUtil(maze, x-1, y, sol) == true)
         {
            printf("\n");
            printMazeSolution(sol);
         }
        }
        /* Move right */
        if ((mazeProblemUtil(maze, x, y+1, sol) == true) )
        {
            printf("\n");                  
            printMazeSolution(sol);
        }
        /* Move down */
        if (mazeProblemUtil(maze, x+1, y, sol) == true)
        {
            printf("\n");
            printMazeSolution(sol);
        }
        /* Move left */
        if(y > 0)
        {
         if (mazeProblemUtil(maze, x, y-1, sol) == true)
         {
            printf("\n");
            printMazeSolution(sol);
         }
        }

        /* Backtrack if no path*/
        sol[x][y] = 0;
        return false;
    }

    return false;
}
void mazeProblem(int maze[M][N])
{
   /*Output Matrix can be differ with dimension with i/p Matrix Dimension*/
    int sol[M][N] = {
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0}
    };

    mazeProblemUtil(maze, 0, 0, sol);
 
}

i/p:-


    int maze[M][N]  =  {
        {1, 1, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {1, 1, 0, 0, 0},
        {1, 0, 1, 1, 1},
        {1, 1, 1, 0, 1}
    };

Type Casting in C++

There are mainly four kinds of casting available in C++ to support different casting operations and also to overcome the different casting problems in C.


Static_cast--
-To convert non polymorphic types.
-This cast type uses information available at compile time to perform the required type conversion.
-Static_cast is not as safe as dynamic_cast, because it does not have the run time check, for example, for ambiguous pointer, static_cast may return successful but a dynamic_cast pointer will fail.

Const_cast--
To add or remove the const-ness or volatile-ness type.
Const-ness removal also can be achieved by using the mutable specifier.



Dynamic_cast--
To convert polymorphic types.
The dynamic_cast operator performs type conversions at run time.

Example:-
struct A {
virtual ~A() { };
};

struct B : A { };

int main() {
B bobj;
A* ap = &bobj;
void * vp = dynamic_cast(ap);
}

Reinterpret_cast--
For type conversion of unrelated types.
Need more attentions for applying this casting. 

Maze Problem with Two directional(right and down) Movement for all the possible Path from Source to destination

Algo:-

1) Start with position(x=0,y=0) 
2) Check, it is valid or not. if Valid then, mark it with 1.
3) Move towards Right, then follow step 2.
4) Move towards Down, then follow step 2.
5) Print all the mark position

Code:-


#define N 4

bool mazeProblemUtil(int maze[N][N], int x, int y, int sol[N][N]);

/* A utility function to print solution  */
void printMazeSolution(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");
    }
}

/* Check if x,y is valid index for N*N maze */
bool isSafeMark(int maze[N][N], int x, int y)
{
    // if (x,y outside maze) return false
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;

    return false;
}


/* Utility function to solve Maze problem */
bool mazeProblemUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    /* Reached Target*/
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }
    int cnt = 0;

    if(isSafeMark(maze, x, y) == true)
    {
        // mark as part of solution path
        sol[x][y] = 1;

        /* moving Right  */
        if ((mazeProblemUtil(maze, x, y+1, sol) == true) )
        {
            printf("\n");                    
            printMazeSolution(sol);
        }
       

        /* moving Down */
        if (mazeProblemUtil(maze, x+1, y, sol) == true)
        {
            printf("\n");
            printMazeSolution(sol);
        }

        /* Backtrack if not matching */
        sol[x][y] = 0;
        return false;
    }  
    return false;
}


void mazeProblem(int maze[N][N])
{
   /* O/p matrix will change with different input matrix dimension*/
    int sol[N][N] = { {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };

    mazeProblemUtil(maze, 0, 0, sol);
}

i/p:-


 int maze[N][N]  =  {
        {1, 1, 0, 0},
        {1, 1, 1, 1},
        {1, 0, 0, 1},
        {1, 1, 1, 1}
    };