AcWing 1101. BFS-Java
原题链接
简单
作者:
zlnnjit
,
2021-02-10 11:53:57
,
所有人可见
,
阅读 325
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
private static char[][] data;
private static int r, c;
private static final int[] dx = new int[]{-1, 0, 1, 0};
private static final int[] dy = new int[]{0, 1, 0, -1};
private static int bfs(int[] start) {
LinkedList<int[]> queue = new LinkedList<>();
int[][] dist = new int[r + 1][c + 1];
queue.add(start);
while (!queue.isEmpty()) {
int[] poll = queue.poll();
int curX = poll[0], curY = poll[1];
for (int i = 0; i < 4; i++) {
int a = curX + dx[i], b = curY + dy[i];
if (a > 0 && a <= r && b > 0 && b <= c && data[a][b] != '#' && dist[a][b] == 0) {
dist[a][b] = dist[curX][curY] + 1;
if (data[a][b] == 'E') return dist[a][b];
queue.add(new int[]{a, b});
}
}
}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = Integer.parseInt(sc.nextLine());
while (count-- > 0) {
String[] split = sc.nextLine().split(" ");
r = Integer.parseInt(split[0]);
c = Integer.parseInt(split[1]);
data = new char[r + 1][c + 1];
int[] start = new int[2];
for (int i = 1; i <= r; i++) {
String s = sc.nextLine();
for (int j = 1; j <= c; j++) {
data[i][j] = s.charAt(j - 1);
if (data[i][j] == 'S') start = new int[]{i, j};
}
}
int res = bfs(start);
String ans = res == 0 ? "oop!" : String.valueOf(res);
System.out.println(ans);
}
}
}