BFS30分 后面的点全部MLE (JAVA)
查看原帖
BFS30分 后面的点全部MLE (JAVA)
694551
Hao_223777楼主2022/4/5 21:47

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int m = scan.nextInt();
		int n = scan.nextInt();
		boolean[][] vis = new boolean[m][n];
		int[][] res = new int[m][n];
		int h = scan.nextInt();
		int g = scan.nextInt();
		Queue<Node> queue = new LinkedList<>();
		Node start = new Node(h - 1, g - 1, 0);
		queue.add(start);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (i == h - 1 && j == g - 1)
					continue;
				res[i][j] = -1;
			}
		}
		while (!queue.isEmpty()) {
			Node poll = queue.poll();
			int x = poll.x;
			int y = poll.y;
			int deepth = poll.deepth;
			vis[x][y] = true;
			if (x + 2 < m && y + 1 < n && !vis[x + 2][y + 1]) {
				res[x + 2][y + 1] = deepth + 1;
				queue.offer(new Node(x + 2, y + 1, deepth + 1));

			}
			if (x + 1 < m && y + 2 < n && !vis[x + 1][y + 2]) {
				res[x + 1][y + 2] = deepth + 1;
				queue.offer(new Node(x + 1, y + 2, deepth + 1));
			}
			if (x - 2 >= 0 && y + 1 < n && !vis[x - 2][y + 1]) {
				res[x - 2][y + 1] = deepth + 1;
				queue.offer(new Node(x - 2, y + 1, deepth + 1));
			}
			if (x - 1 >= 0 && y + 2 < n && !vis[x - 1][y + 2]) {
				res[x - 1][y + 2] = deepth + 1;
				queue.offer(new Node(x - 1, y + 2, deepth + 1));
			}
			if (x - 1 >= 0 && y - 2 >= 0 && !vis[x - 1][y - 2]) {
				res[x - 1][y - 2] = deepth + 1;
				queue.offer(new Node(x - 1, y - 2, deepth + 1));
			}
			if (x - 2 >= 0 && y - 1 >= 0 && !vis[x - 2][y - 1]) {
				res[x - 2][y - 1] = deepth + 1;
				queue.offer(new Node(x - 2, y - 1, deepth + 1));
			}
			if (x + 1 < m && y - 2 >= 0 && !vis[x + 1][y - 2]) {
				res[x + 1][y - 2] = deepth + 1;
				queue.offer(new Node(x + 1, y - 2, deepth + 1));
			}
			if (x + 2 < m && y - 1 >= 0 && !vis[x + 2][y - 1]) {
				res[x + 2][y - 1] = deepth + 1;
				queue.offer(new Node(x + 2, y - 1, deepth + 1));
			}
		}

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				System.out.printf("%-5d", res[i][j]);
			}
			System.out.println();
		}
	}

	static public class Node {
		int x;
		int y;
		int deepth;

		public Node(int x, int y, int deepth) {
			this.x = x;
			this.y = y;
			this.deepth = deepth;
		}
	}
}

2022/4/5 21:47
加载中...