Java BFS #10MLE 各位大佬要怎么优化
  • 板块P1746 离开中山路
  • 楼主cxcs
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/24 01:12
  • 上次更新2023/11/24 15:08:19
查看原帖
Java BFS #10MLE 各位大佬要怎么优化
978815
cxcs楼主2023/11/24 01:12
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	// n地图数组大小  起点位置(startx, starty)    终点位置(endx, endy)
	static int n, startx, starty, endx, endy;
	static int map[][];   // 地图数组, 接收输入 0通1阻   下标1开始
	static int dist[][];  // 该点到出发点 距离   		   下标1开始
	
	// i=0时, dx=-1 dy=0 向上移一格     i=1, 右移一格
	// bfs顺序: 上 右 下 左
	static int dx[] = {-1, 0, 1, 0};  
	static int dy[] = {0, 1, 0, -1};  
	
	
	public static int bfs(int x, int y) {
		// 1. 初始化dist数组为 -1, 为走过
		for(int i = 1; i < dist.length; i++)
			Arrays.fill(dist[i], -1);   // 该方法只能给二维数组赋值
		
		// 2. 创建队列  LinkedList<Node>也可以
		Queue<Node> queue = new LinkedList<>();
		// 3. 创建首节点, 加入队列
		Node first = new Node(x, y);
		queue.offer(first);   // offer 或 add 入队
		
		dist[x][y] = 0;  // 首节点出发, 标记距离0
		
		// 4. 循环, 队列为空 bfs结束
		while(!queue.isEmpty()) {
			// 1. 弹出队首(最先入队的)
			first = queue.poll();   // peek获得队首(不删除)
			
			int a, b;
			// 2. 循环 向四个方向移动: 上 右 下 左
			for(int i = 0; i < 4; i++) {
				// 1).获取下一次移动的位置
				a = first.x + dx[i];
				b = first.y + dy[i];
				
				// 2). 位置判定
				if(a < 1 || a > n || b < 1 || b > n)  // 1开始, 数组越界
					continue;
				if(map[a][b] != 0)  // 此点不同, 不为0堵住
					continue;
				if(dist[a][b] > 0)  // 此点走过
					continue;
				
				// 3). 选择该点
				Node node = new Node(a, b);   // 创建节点
				queue.offer(node);   // 入队
				dist[a][b] = dist[first.x][first.y] + 1;  // 标记距离: 上一点到起点距离+1 
				
				// 4). 到达终点  返回距离数组dist 终点值
				if(a == endx && b == endy)
					return dist[endx][endy];
			}
		}
		
		return dist[endx][endy];
	}
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();    // 规模

		map = new int[n+1][n+1];
		dist = new int[n+1][n+1];
		// 数之间没有空格 接收为Stiing 再改为int
		String str[];
		for(int i = 1; i < map.length; i++) {
			str = sc.next().split(""); 
			for(int j = 1; j < map[0].length; j++) {
				map[i][j] = Integer.valueOf(str[j-1]);
			}
		}
		
		startx = sc.nextInt();
		starty = sc.nextInt();
		endx = sc.nextInt();
		endy = sc.nextInt();
		sc.close();
			
		System.out.println(bfs(startx, starty));
		
	}
}	

// 节点类
class Node {
	int x;
	int y;
	
	public Node(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}
2023/11/24 01:12
加载中...