AcWing 188. 武士风度的牛(Java)模板级写法
原题链接
简单
作者:
执梗
,
2022-04-26 16:52:58
,
所有人可见
,
阅读 147
import java.util.*;
public class Main {
static int N=160;
static int c,r;
static char[][] a=new char[N][N];
static int[] dx={-2,-2,-1,-1,1,1,2,2};
static int[] dy={-1,1,2,-2,2,-2,1,-1};
static boolean[][] st=new boolean[N][N];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
c=sc.nextInt();
r=sc.nextInt();
int startX=0;
int startY=0;
int endX=0;
int endY=0;
for (int i = 0; i <r; i++) {
a[i]=sc.next().toCharArray();
for (int j = 0; j <c ; j++) {
if (a[i][j]=='K'){
startX=i;
startY=j;
}else if (a[i][j]=='H'){
endX=i;
endY=j;
}
}
}
Queue<int[]> queue=new LinkedList<>();
queue.offer(new int[]{startX,startY});
st[startX][startY]=true;
int tmp=0;
while (!queue.isEmpty()){
int size=queue.size();
while (size-->0){
int[] curr=queue.poll();
int x=curr[0];
int y=curr[1];
if (x==endX&&y==endY){
System.out.println(tmp);
return;
}
for (int i = 0; i <8; i++) {
int newX=x+dx[i];
int newY=y+dy[i];
if (!(newX>=0&&newX<r&&newY>=0&&newY<c)) continue;
if (a[newX][newY]=='*') continue;
if (st[newX][newY]) continue;
queue.offer(new int[]{newX,newY});
st[newX][newY]=true;
}
}
tmp++;
}
}
}