Skip to main content

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;
            }
        }
    }
}

Labels:

Comments

Post a Comment

Popular posts from this blog

40 Redis interview questions for 2021 - 2022

  Redis interview questions 1.What is Redis?. 2. What is the data type of Redis? 3. What are the benefits of using Redis? 4. What are the advantages of Redis over Memcached? 5. What are the differences between Memcache and Redis? 6. Is Redis single-process and single-threaded? 7. What is the maximum storage capacity of a string type value? 8. What is the persistence mechanism of Redis? Their advantages and disadvantages? 9. Redis common performance problems and solutions: 10. What is the deletion strategy of redis expired keys? 11. Redis recycling strategy (elimination strategy)? 12. Why does edis need to put all data in memory? 13. Do you understand the synchronization mechanism of Redis? 14. What are the benefits of Pipeline? Why use pipeline? 15. Have you used Redis cluster? What is the principle of cluster? 16. Under what circumstances will the Redis cluster solution cause the entire cluster to be unavailable? 17. What are the Java clients supp...
Post a Comment
Read more

8 common methods for server performance optimization

  1. Use an in-memory database In-memory database is actually a database that puts data in memory and operates directly. Compared with the disk, the data read and write speed of the memory is several orders of magnitude higher. Saving the data in the memory can greatly improve the performance of the application compared to accessing it from the disk. The memory database abandoned the traditional way of disk data management, redesigned the architecture based on all data in memory, and made corresponding improvements in data caching, fast algorithms, and parallel operations, so the data processing speed is faster than that of traditional databases. Data processing speed is much faster.       But the problem of security can be said to be the biggest flaw in the memory database. Because the memory itself has the natural defect of power loss, when we use the memory database, we usually need to take some protection mechanisms for the data on the memory in advance, such...
Post a Comment
Read more