JAVA program to help jerry find cheese

ALGORITHM:

Jerry is hungry and needs cheese. Bur cheese is in a maze and jerry needs help to find the cheese.
The maze solving is a classic algorithm under backtracking and ai.The problem is to find a path for the rat to food in a maze.
The problem can be solved trying out different paths possible and find the right path,
This logic can be implemented by a simple recursive algorithm. Since the jerryis performed in stack the processes are done in LIFO manner so if we have to print instructions to jerry we will do the process as cheese finds jerry.

1. Start with the target
2. If the cell is not legal (if it is out of maze or the cell is a wall) return false
3. If starting point has reached return true 
4. else make the cell a wall(to avoid coming back to the same path from any other instant) and
5. Take all the cells in  four direction and check whether the path can be reached through any of these cells and print opposite movement if the cell is a part of the path (eg if upper cell is part of path print DOWN)and return true and if not path backtrack and return false.These cells should chosen according to the distance to starting point from the current point.

  

The above maze is:

1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 0
1 1 1 1 0

So the jerry should move down four times and right three times and up two times and right and then up two times.

CODE:

import java.util.Scanner;

public class Maze{
   
   
    static Scanner in = new Scanner(System.in);
    static int[][] maze;

    static boolean solveMaze(int x,int y,int tx,int ty,int b,int h){

        if(x>=0 && x<b && y>=0 && y<h && maze[x][y]==1){//Checking if current cell is legal
            maze[x][y]-=1;
            if(x==tx && y==ty)//checking if point has reached
                return true;
            boolean up,down,left,right;
            /*

             Calculating horizontal and vertical distances and moving according to it

            */

            int xDiff=tx-x;
            if(xDiff<0)
                xDiff*=-1;
            int yDiff=ty-y;
            if(yDiff<0)
                yDiff*=-1;
            if(xDiff<yDiff){
                if(tx<x){
                    up=solveMaze(x-1,y,tx,ty,b,h);
                    down=solveMaze(x+1,y,tx,ty,b,h);
                }
                else{
                    down=solveMaze(x+1,y,tx,ty,b,h);
                    up=solveMaze(x-1,y,tx,ty,b,h);
                }
                if(ty<y){
                    left=solveMaze(x,y-1,tx,ty,b,h);
                    right=solveMaze(x,y+1,tx,ty,b,h);
                }
                else{
                    right=solveMaze(x,y+1,tx,ty,b,h);
                    left=solveMaze(x,y-1,tx,ty,b,h);
                }
            }
            else{
                if(ty<y){
                    left=solveMaze(x,y-1,tx,ty,b,h);
                    right=solveMaze(x,y+1,tx,ty,b,h);
                }
                else{
                    right=solveMaze(x,y+1,tx,ty,b,h);
                    left=solveMaze(x,y-1,tx,ty,b,h);
                }
                if(tx<x){
                    up=solveMaze(x-1,y,tx,ty,b,h);
                    down=solveMaze(x+1,y,tx,ty,b,h);
                }
                else{
                    down=solveMaze(x+1,y,tx,ty,b,h);
                    up=solveMaze(x-1,y,tx,ty,b,h);
                }
            }

            //print opposite movement if the cell is a part of the path
            if(up||down||left||right){
                if(up)
                    System.out.println("DOWN");
                if(down)
                    System.out.println("UP");
                if(left)
                    System.out.println("RIGHT");
                if(right)
                    System.out.println("LEFT");
                return true;
            }
            maze[x][y]+=1;//backtrack
            return false;
        }
        return false;
    }
    public static void main(String[] args) {
        System.out.println("enter number of rows and columns ");
        System.out.print("Rows: ");
        int b = in.nextInt();
        System.out.print("Columns: ");
        int h = in.nextInt();
        maze=new int[b][h];
        System.out.println("enter maze 1 for path and 0 for wall");
        for(int i=0;i<b;i++)
            for(int j=0;j<h;j++)
                maze[i][j]=in.nextInt();
        System.out.print("Enter Jerry position\nX: ");
        int begx=in.nextInt();
        System.out.print("Y: ");
        int begy=in.nextInt();
        System.out.print("Enter cheese position\nX: ");
        int tarx=in.nextInt();
        System.out.print("Y: ");
        int tary=in.nextInt();
        if(!solveMaze(tarx,tary,begx,begy,b,h))
        System.out.println("no path");
    }
}

OUTPUT:

enter number of rows and columns
Rows: 5
Columns: 5
enter maze 1 for path and 0 for wall
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 0
1 1 1 1 0
Enter Jerry position
X: 0
Y: 0
Enter cheese position
X: 0
Y: 4

DOWN
DOWN
DOWN
DOWN
RIGHT
RIGHT
RIGHT
UP
UP
RIGHT
UP
UP