AcWing 1101. 献给阿尔吉侬的花束java版
原题链接
简单
作者:
BOBCUSO4
,
2024-01-22 17:30:17
,
所有人可见
,
阅读 32
import java.util.*;
public class Main{
static int T,R,C;
static char[][] g = new char[210][210];
static class Node{
int x,y;
public Node() {
}
public Node(int x,int y) {
this.x = x;
this.y = y;
}
}
static int[][] st = new int[210][210];//记录从顶点到某一点走了几步,-1表示没有到这个点
static int[] dx = {-1,0,1,0},dy = {0,1,0,-1};
static Scanner sc = new Scanner(System.in);
static Queue<Node> que = new LinkedList<>();
public static void fun() {
for(int i =0;i<210;i++)
Arrays.fill(st[i],-1);//只能填充一维的
R = sc.nextInt();
C = sc.nextInt();
Node start = new Node();
Node end = new Node();
for(int i =0;i<R;i++) {
String str =sc.next();
g[i] = str.toCharArray();
for(int j =0;j<C;j++) {
if(g[i][j] =='S') {
start.x = i;
start.y = j;
}
if(g[i][j] == 'E') {
end.x = i;
end.y = j;
}
}
}
que.add(start);
st[start.x][start.y] = 0;
while(!que.isEmpty()) {
Node tmp = que.remove();
for(int i = 0;i<4;i++) {
int x1 = tmp.x+dx[i],y1=tmp.y+dy[i];
if(x1<0||x1>=R||y1<0||y1>=C||g[x1][y1] == '#') continue;
if(st[x1][y1]==-1) {
st[x1][y1] = st[tmp.x][tmp.y] +1;
que.add(new Node(x1,y1));
}
}
}
if(st[end.x][end.y]!=-1) System.out.println(st[end.x][end.y]);
else System.out.println("oop!");
}
public static void main(String[] args) {
T = sc.nextInt();
while(T-->0) {
fun();
}
}
}