Recursion-maze problem - Rat in the Maze - Game

 

package com.bei.Demo01_recursion;

public class MiGong {

    public static void main(String[] args) 

{

        //First create a two-dimensional array to simulate the maze

        int [][]map=new int[8][7];

        //Use 1 for wall

        for (int i = 0; i <7 ; i++) {

            map[0][i]=1;

            map[7][i]=1;

        }

        for (int i = 0; i <8 ; i++) {

            map[i][0]=1;

            map[i][6]=1;

        }

        //Set the bezel

        map[3][1]=1;

        map[3][2]=1;

        //Output

        for (int i = 0; i <8 ; i++) {

            for (int j = 0; j < 7; j++) {

                System.out.print(map[i][j]+" ");

            }

            System.out.println();

        }

        System.out.println("----------------------------");

        setWay(map,1,1);

        for (int i = 0; i <8 ; i++) {

            for (int j = 0; j < 7; j++) {

                System.out.print(map[i][j]+" ");

            }

            System.out.println();

        }

    }

    //Use recursive backtracking to find the way to the ball

    //1.mapRepresents the map

    //2.i,j Indicates starting from that location on the map (1,1)

    //2.If you can get to the location of map[6][5], then you can go

    //4Convention: When map[i][j]=0, it means that it has not been found. 1 means that the wall 2 means that the path can be taken. 3 means that the point has been passed but cannot be passed.

    //5.Strategy: Down-Right-Up-Left, if the point cannot be reached, backtrack

    public static boolean setWay(int [][]map,int i,int j){

        if(map[6][5]==2){

            return true;

        }else{

            if(map[i][j]==0){

                map[i][j]=2;

                if(setWay(map,i+1,j)){

                    return true;

                }else if(setWay(map,i,j+1)){

                    return true;

                }else if(setWay(map,i-1,j)){

                    return true;

                }else if(setWay(map,i,j-1)){

                    return true;

                }else {

                    map[i][j]=3;

                    return false;

                }

            }else {

                return false;

            }

        }

    }

}