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)

The settings.json file is located in the user-level or workspace-level path and is used to customize VSCode settings. 1. User-level path: Windows is C:\Users\\AppData\Roaming\Code\User\settings.json, macOS is /Users//Library/ApplicationSupport/Code/User/settings.json, Linux is /home//.config/Code/User/settings.json; 2. Workspace-level path: .vscode/settings in the project root directory

To correctly handle JDBC transactions, you must first turn off the automatic commit mode, then perform multiple operations, and finally commit or rollback according to the results; 1. Call conn.setAutoCommit(false) to start the transaction; 2. Execute multiple SQL operations, such as INSERT and UPDATE; 3. Call conn.commit() if all operations are successful, and call conn.rollback() if an exception occurs to ensure data consistency; at the same time, try-with-resources should be used to manage resources, properly handle exceptions and close connections to avoid connection leakage; in addition, it is recommended to use connection pools and set save points to achieve partial rollback, and keep transactions as short as possible to improve performance.

DependencyInjection(DI)isadesignpatternwhereobjectsreceivedependenciesexternally,promotingloosecouplingandeasiertestingthroughconstructor,setter,orfieldinjection.2.SpringFrameworkusesannotationslike@Component,@Service,and@AutowiredwithJava-basedconfi

itertools.combinations is used to generate all non-repetitive combinations (order irrelevant) that selects a specified number of elements from the iterable object. Its usage includes: 1. Select 2 element combinations from the list, such as ('A','B'), ('A','C'), etc., to avoid repeated order; 2. Take 3 character combinations of strings, such as "abc" and "abd", which are suitable for subsequence generation; 3. Find the combinations where the sum of two numbers is equal to the target value, such as 1 5=6, simplify the double loop logic; the difference between combinations and arrangement lies in whether the order is important, combinations regard AB and BA as the same, while permutations are regarded as different;

java.lang.OutOfMemoryError: Javaheapspace indicates insufficient heap memory, and needs to check the processing of large objects, memory leaks and heap settings, and locate and optimize the code through the heap dump analysis tool; 2. Metaspace errors are common in dynamic class generation or hot deployment due to excessive class metadata, and MaxMetaspaceSize should be restricted and class loading should be optimized; 3. Unabletocreatenewnativethread due to exhausting system thread resources, it is necessary to check the number of threads, use thread pools, and adjust the stack size; 4. GCoverheadlimitexceeded means that GC is frequent but has less recycling, and GC logs should be analyzed and optimized.

fixture is a function used to provide preset environment or data for tests. 1. Use the @pytest.fixture decorator to define fixture; 2. Inject fixture in parameter form in the test function; 3. Execute setup before yield, and then teardown; 4. Control scope through scope parameters, such as function, module, etc.; 5. Place the shared fixture in conftest.py to achieve cross-file sharing, thereby improving the maintainability and reusability of tests.

TheJVMenablesJava’s"writeonce,runanywhere"capabilitybyexecutingbytecodethroughfourmaincomponents:1.TheClassLoaderSubsystemloads,links,andinitializes.classfilesusingbootstrap,extension,andapplicationclassloaders,ensuringsecureandlazyclassloa

Use classes in the java.time package to replace the old Date and Calendar classes; 2. Get the current date and time through LocalDate, LocalDateTime and LocalTime; 3. Create a specific date and time using the of() method; 4. Use the plus/minus method to immutably increase and decrease the time; 5. Use ZonedDateTime and ZoneId to process the time zone; 6. Format and parse date strings through DateTimeFormatter; 7. Use Instant to be compatible with the old date types when necessary; date processing in modern Java should give priority to using java.timeAPI, which provides clear, immutable and linear
