题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.*;
class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
List[HTML_REMOVED] res = new ArrayList<>();
for (int k = 0; k < T; k) {
int n = sc.nextInt(), m = sc.nextInt();
char[][] maze = new char[n][m];
int[] start = null, destination = null;
sc.nextLine();
for (int i = 0; i < n; i) {
String s = sc.nextLine();
for (int j = 0; j < m; j++) {
maze[i][j] = s.charAt(j);
if (s.charAt(j) == ‘S’) start = new int[]{i, j};
if (s.charAt(j) == ‘E’) destination = new int[]{i, j};
}
}
int temp = findMaze(maze, n, m, start, destination);
if (temp > 0) {
res.add(“” + temp);
} else {
res.add(“oop!”);
}
}
for (String s : res) System.out.println(s);
}
public static int findMaze(char[][] maze, int n, int m, int[] start, int[] destination) {
Queue<int[]> queue = new LinkedList<>();
int step = 0;
boolean[][] visited = new boolean[n][m];
queue.offer(new int[]{start[0], start[1]});
visited[start[0]][start[1]] = true;
int[] drow = {1, 0, -1, 0}, dcol = {0, 1, 0, -1};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
if (cur[0] == destination[0] && cur[1] == destination[1]) return step;
for (int j = 0; j < 4; j++) {
int nr = cur[0] + drow[j], nc = cur[1] + dcol[j];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || visited[nr][nc] || maze[nr][nc] == '#') continue;
queue.offer(new int[]{nr, nc});
visited[nr][nc] = true;
}
}
step++;
}
return -1;
}
}