AcWing 1101. 献给阿尔吉侬的花束-Java
原题链接
简单
作者:
Jiang锋时刻
,
2021-02-03 13:17:45
,
所有人可见
,
阅读 380
Java 代码
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int row;
static int col;
static char[][] arr;
static int[][] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
while(count-- > 0) {
row = sc.nextInt();
col = sc.nextInt();
arr = new char[row][col];
visited = new int[row][col];
for(int i = 0; i < row; i++) {
String str = sc.next();
arr[i] = str.toCharArray();
}
int[] st = new int[2];
int[] ed = new int[2];
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(arr[i][j] == 'S') {
st = new int[]{i, j};
}
}
}
System.out.println(bfs(st));
}
}
public static String bfs(int[] st) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{st[0], st[1]});
arr[st[0]][st[1]] = '#';
while(!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0];
int y = cur[1];
for(int d = 0; d < 4; d++) {
int x1 = x + dx[d];
int y1 = y + dy[d];
if(x1 < 0 || y1 < 0 || x1 >= row || y1 >= col ||arr[x1][y1] == '#' ) {
continue;
}
if(arr[x1][y1] == 'E') {
return visited[x][y] + 1 + "";
}
visited[x1][y1] = visited[x][y] + 1;
arr[x1][y1] = '#';
queue.add(new int[]{x1, y1});
}
}
return "oop!";
}
}