Use java algorithm BFS to find the shortest path to the maze exit
Nov 10, 2020 pm 03:38 PMEstablishment of queue
static Queue r = new LinkedList(); //創(chuàng)建隊(duì)列
(Learning video sharing: java course)
Basic method of queue
r.offer(); Enter the end of the queue
r.poll(); Exit the first part of the queue
r.peek(); Contents of the first part of the queue
Code implementation :
Global variable setting
package Two; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class BFS { static int a[][] = new int [100][100]; //輸入迷宮 static int v[][] = new int [100][100]; //走過的標(biāo)記為1 static int startx,starty; //輸入起點(diǎn)位置 static int p,q; //輸入要到達(dá)的坐標(biāo)位置 static int dx[] = {0,1,0,-1}; //方向數(shù)組 static int dy[] = {1,0,-1,0}; static Queue<point> r = new LinkedList<point>(); //創(chuàng)建隊(duì)列 static class point{ //建立類坐標(biāo)屬性 int x; int y; int step; }
Input the maze and starting position, target position
public static void main(String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in .nextInt(); for(int i=1;i<=m;i++) //輸入迷宮 for(int j=1;j<=n;j++) a[i][j] = in.nextInt(); startx = in.nextInt(); starty = in.nextInt(); //輸入目標(biāo)和起始位置 p = in.nextInt(); q = in.nextInt();
BFS algorithm start
1. Set the team leader
//BFS point start = new point(); //定義一個(gè)初始類作為隊(duì)首 start.x = startx; start.y = starty; start.step = 0; r.offer(start); v[startx][starty]=1;
2. Enter the loop body
while(!r.isEmpty()) { //當(dāng)隊(duì)列為空時(shí)跳出循環(huán) int x = r.peek().x; //把隊(duì)首的屬性賦值 int y = r.peek().y; int step = r.peek().step; if(x==p && y==q) { //到達(dá)目的地,退出循環(huán) System.out.println(step); break; } for(int i=0;i<4;i++) { //廣度遍歷,右下左上分別入隊(duì) int tx= x+dx[i]; int ty= y+dy[i]; if(a[tx][ty] == 1 && v[tx][ty]==0) { //判斷是否可以入隊(duì) //入隊(duì) point temp = new point(); //建立一個(gè)臨時(shí)類 temp.x = tx; temp.y = ty; temp.step = r.peek().step +1; r.offer(temp); //入隊(duì) v[tx][ty]=1; //標(biāo)記為1 } } r.poll(); //拓展完了需要隊(duì)首出隊(duì) } } }
Related recommendations:Getting started with java
The above is the detailed content of Use java algorithm BFS to find the shortest path to the maze exit. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

Java supports asynchronous programming including the use of CompletableFuture, responsive streams (such as ProjectReactor), and virtual threads in Java19. 1.CompletableFuture improves code readability and maintenance through chain calls, and supports task orchestration and exception handling; 2. ProjectReactor provides Mono and Flux types to implement responsive programming, with backpressure mechanism and rich operators; 3. Virtual threads reduce concurrency costs, are suitable for I/O-intensive tasks, and are lighter and easier to expand than traditional platform threads. Each method has applicable scenarios, and appropriate tools should be selected according to your needs and mixed models should be avoided to maintain simplicity

JavaNIO is a new IOAPI introduced by Java 1.4. 1) is aimed at buffers and channels, 2) contains Buffer, Channel and Selector core components, 3) supports non-blocking mode, and 4) handles concurrent connections more efficiently than traditional IO. Its advantages are reflected in: 1) Non-blocking IO reduces thread overhead, 2) Buffer improves data transmission efficiency, 3) Selector realizes multiplexing, and 4) Memory mapping speeds up file reading and writing. Note when using: 1) The flip/clear operation of the Buffer is easy to be confused, 2) Incomplete data needs to be processed manually without blocking, 3) Selector registration must be canceled in time, 4) NIO is not suitable for all scenarios.

In Java, enums are suitable for representing fixed constant sets. Best practices include: 1. Use enum to represent fixed state or options to improve type safety and readability; 2. Add properties and methods to enums to enhance flexibility, such as defining fields, constructors, helper methods, etc.; 3. Use EnumMap and EnumSet to improve performance and type safety because they are more efficient based on arrays; 4. Avoid abuse of enums, such as dynamic values, frequent changes or complex logic scenarios, which should be replaced by other methods. Correct use of enum can improve code quality and reduce errors, but you need to pay attention to its applicable boundaries.

Singleton design pattern in Java ensures that a class has only one instance and provides a global access point through private constructors and static methods, which is suitable for controlling access to shared resources. Implementation methods include: 1. Lazy loading, that is, the instance is created only when the first request is requested, which is suitable for situations where resource consumption is high and not necessarily required; 2. Thread-safe processing, ensuring that only one instance is created in a multi-threaded environment through synchronization methods or double check locking, and reducing performance impact; 3. Hungry loading, which directly initializes the instance during class loading, is suitable for lightweight objects or scenarios that can be initialized in advance; 4. Enumeration implementation, using Java enumeration to naturally support serialization, thread safety and prevent reflective attacks, is a recommended concise and reliable method. Different implementation methods can be selected according to specific needs

Anonymous internal classes are used in Java to create subclasses or implement interfaces on the fly, and are often used to override methods to achieve specific purposes, such as event handling in GUI applications. Its syntax form is a new interface or class that directly defines the class body, and requires that the accessed local variables must be final or equivalent immutable. Although they are convenient, they should not be overused. Especially when the logic is complex, they can be replaced by Java8's Lambda expressions.

String is immutable, StringBuilder is mutable and non-thread-safe, StringBuffer is mutable and thread-safe. 1. Once the content of String is created cannot be modified, it is suitable for a small amount of splicing; 2. StringBuilder is suitable for frequent splicing of single threads, and has high performance; 3. StringBuffer is suitable for multi-threaded shared scenarios, but has a slightly lower performance; 4. Reasonably set the initial capacity and avoid using String splicing in loops can improve performance.

The COALESCE function is used to return the first non-null value in the parameter list and is suitable for processing NULL data. 1. The basic usage is to replace the NULL value, such as replacing the empty field with the default contact method; 2. It can be used to set the default value in aggregate query to ensure that 0 is returned instead of NULL when there is no data; 3. It can be used in conjunction with other functions such as NULLIF and IFNULL to enhance data cleaning and logical judgment capabilities.

Annotation processor is an extended mechanism in the Java compilation stage, used to scan and process annotations in the source code, and can generate new code or preprocess it. Its core functions include: 1. When defining annotations, it needs to specify the retention policy and target element type; 2. Implement the AbstractProcessor class and rewrite key methods such as getSupportedAnnotationTypes, getSupportedSourceVersion and process; 3. Register the processor to declare a fully qualified name through a configuration file in the META-INF/services directory. Annotation processors are widely used in frameworks such as Dagger, ButterKnife and Roo
