Rat Maze With Multiple Jumps Java

PROGRAM TO SOLVE RAT IN A MAZE PROBLEM



class MAIN
{
 
    // Maze size
    static int N = 4;
 
    /* A utility function to print solution matrix
    sol[N][N] */
    static void printSolution(int sol[][])
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                System.out.printf(" %d ", sol[i][j]);
            }
            System.out.printf("\n");
        }
    }
 
    /* A utility function to check if x, y is valid
    index for N*N maze */
    static boolean isSafe(int maze[][], int x, int y)
    {
         
        // if (x, y outside maze) return false
        if (x >= 0 && x < N && y >= 0 &&
             y < N && maze[x][y] != 0)
        {
            return true;
        }
 
        return false;
    }
 
    /* This function solves the Maze problem using
    Backtracking. It mainly uses solveMazeUtil() to
    solve the problem. It returns false if no path
    is possible, otherwise return true and prints
    the path in the form of 1s. Please note that
    there may be more than one solutions,
    this function prints one of the feasible solutions.*/
    static boolean solveMaze(int maze[][])
    {
        int sol[][] = {{0, 0, 0, 0},
                       {0, 0, 0, 0},
                       {0, 0, 0, 0},
                       {0, 0, 0, 0}};
 
        if (solveMazeUtil(maze, 0, 0, sol) == false)
        {
            System.out.printf("Solution doesn't exist");
            return false;
        }
 
        printSolution(sol);
        return true;
    }
 
    /* A recursive utility function to solve Maze problem */
    static boolean solveMazeUtil(int maze[][], int x,
                                 int y, int sol[][])
    {
        // if (x, y is goal) return true
        if (x == N - 1 && y == N - 1)
        {
            sol[x][y] = 1;
            return true;
        }
 
        // Check if maze[x][y] is valid
        if (isSafe(maze, x, y) == true)
        {
 
            // mark x, y as part of solution path
            sol[x][y] = 1;
 
            /* Move forward in x direction */
            for (int i = 1; i <= maze[x][y] && i < N; i++)
            {
 
                /* Move forward in x direction */
                if (solveMazeUtil(maze, x + i, y, sol) == true)
                {
                    return true;
                }
 
                /* If moving in x direction doesn't give
                solution then Move down in y direction */
                if (solveMazeUtil(maze, x, y + i, sol) == true)
                {
                    return true;
                }
            }
 
            /* If none of the above movements work then
            BACKTRACK: unmark x, y as part of solution
            path */
            sol[x][y] = 0;
            return false;
        }
 
        return false;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int maze[][] = {{2, 1, 0, 0},
                        {3, 0, 0, 1},
                        {0, 1, 0, 1},
                        {0, 0, 0, 1}};
 
        solveMaze(maze);
    }
}

OUTPUT:
1  0  0  0 
1  0  0  1 
0  0  0  1 
0  0  0  1

Comments

Post a Comment

Popular posts from this blog

Solve the Sudoku Python

PROGRAM TO SOLVE SUDOKU # A Utility Function to print the Grid def print_grid(arr):      for i in range ( 9 ):          for j in range ( 9 ):              print arr[i][j],          print ( 'n' )              # Function to Find the entry in # the Grid that is still  not used # Searches the grid to find an # entry that is still unassigned. If # found, the reference parameters # row, col will be set the location # that is unassigned, and true is # returned. If no unassigned entries # remains, false is returned. # 'l' is a list  variable that has # been passed from the solve_sudoku function # to keep track of incrementation # of Rows and Columns def find_empty_location(arr, l):      for row in range ( 9 ):       ...
Read more

Solve the Sudoku Java

PROGRAM TO SOLVE SUDOKU class GFG {      public static boolean isSafe( int [][] board,                                   int row, int col,                                   int num)      {          // Row has the unique (row-clash)          for ( int d = 0 ; d < board.length; d++)          {                             // Check if the number we are trying to   ...
Read more

Find Duplicates Java

PROGRAM TO FIND REPEATING NUMBERS IN AN ARRAY class MAIN {           public static void main(String args[]) {          int numRay[] = { 0 , 4 , 3 , 2 , 7 , 8 , 2 , 3 , 1 };               for ( int i = 0 ; i < numRay.length; i++) {              numRay[numRay[i] %  numRay.length] = numRay[numRay[i] %  numRay.length] + numRay.length;          }          System.out.println( "The repeating elements are : " );          for ( int i = 0 ; i < numRay.length; i++) {              if (numRay[i] >= numRay.length* 2 ) {                ...
Read more