AcWing 3179. 穿越雷区
原题链接
简单
作者:
不知名路人
,
2021-04-09 21:20:18
,
所有人可见
,
阅读 382
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class My{
int x,y;
My(int x,int y){
this.x=x;
this.y=y;
}
}
public class Main {
static int N=110;
static int n;
static String[][] g=new String[N][N];
static int[][] dist=new int[N][N];
static boolean[][] st=new boolean[N][N];
static int[] dx={0, 1, 0, -1};
static int[] dy={-1, 0, 1, 0};
static My s,e;
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
n=in.nextInt();
//因为敲一个回车 所以下面的字符串用来装这个回车
String ll=in.nextLine();
//读入数据
for(int i=0;i<n;i++){
g[i]=in.nextLine().split("\\s++");
}
//找起点和终点
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j].equals("A")){
s=new My(i,j);
}
if(g[i][j].equals("B")){
e=new My(i,j);
}
}
}
System.out.println(bfs(s,e));
}
static String bfs(My s,My e){
Queue<My> q=new LinkedList<>();//队列
q.offer(s);//起始位置放进队列
st[s.x][s.y]=true;//起始位置标记
dist[s.x][s.y]=0;//计算步数。
while (!q.isEmpty()){
My t=q.poll();//取出当前坐标
for(int i=0;i<4;i++){
int x=t.x+dx[i];
int y=t.y+dy[i];
//越界或者+ +, - - 都continue
if(x<0||x>=n||y<0||y>=n||st[x][y]||g[x][y].equals(g[t.x][t.y])){
continue;
}
dist[x][y]=dist[t.x][t.y]+1;
q.offer(new My(x,y));
st[x][y]=true;
if(e.x==x&&e.y==y){
return ""+dist[x][y];
}
}
}
return "-1";
}
}