asp网站中停止后面代码的运行,阐述企业搭建网站的重要性,网络策略,wordpress摘要字数题目#xff1a;
解题思路#xff1a; 简单的广度优先算法#xff08;BFS#xff09;
BFS 的特性
按层次遍历#xff1a;BFS 按照节点的距离#xff08;边的数量#xff09;来逐层访问节点。保证最短路径#xff1a;对于无权图#xff08;所有边权重相同#xff0…题目
解题思路 简单的广度优先算法BFS
BFS 的特性
按层次遍历BFS 按照节点的距离边的数量来逐层访问节点。保证最短路径对于无权图所有边权重相同BFS 能够找到从起点到任何其他节点的最短路径。避免回路通过使用已访问标记visited 数组可以防止重复访问同一个节点从而避免无限循环。队列结构使用队列来管理待访问的节点。
import java.util.Scanner;
import java.util.Queue;
import java.util.ArrayDeque;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {//方向static int[] dx {0, 0, -1, 1};static int[] dy {1, -1, 0, 0};//标记是否走过static boolean[][] visted;//矩阵大小static int N, M;//入口、出口位置static int startx, starty, endx, endy; public static void main(String[] args) {Scanner scan new Scanner(System.in);//在此输入您的代码...N scan.nextInt();M scan.nextInt();int [][] arr new int[N][M];visted new boolean[N][M];for (int i 0; i N; i) {for (int j 0; j M; j) {arr[i][j] scan.nextInt(); }}startx scan.nextInt();starty scan.nextInt();endx scan.nextInt();endy scan.nextInt();System.out.println(bfs(arr, startx - 1, starty - 1));scan.close();}public static int bfs(int[][] arr, int x, int y) {//创建队列更新位置Queueint[] q new ArrayDeque();q.offer(new int[] {x, y, 0});while(!q.isEmpty()) {int[] poll q.poll();int x1 poll[0];int y1 poll[1];int steps poll[2];//判断是否到达终点if (x1 endx-1 y1 endy-1) {return steps;}//根据四个方向走下一步for (int i 0; i 4; i) {int xx x1 dx[i];int yy y1 dy[i];if (xx 0 yy 0 xx N yy M !visted[xx][yy] arr[xx][yy] 1) {visted[xx][yy] true;q.offer(new int[] {xx, yy, steps 1});}}}return -1;}
}
