由于该题与此题如出一辙,非常适合练习和巩固!
1.题目描述
众所周知,Teutonic Knight是某RTS游戏中,移动速度最快的角色。而且他热衷于参加赛跑比赛。现在他想知道他最快需要用多长时间才可以到达终点,假设他没有开加速挂。 起初,他站在第1张图的某个位置(用‘S’标识),终点在第k张图的某个位置(用‘E’标识),在除最后一张图外,每一张图上有且仅有一个传送点(用‘T’标识),可以将他传送到下一张图的某个位置,用‘t’标识。传送不需要任何时间,可以理解为瞬间完成。每次移动一个单位距离耗时1秒。 现在Teutonic Knight想知道他在全程狂奔的情况下,最快需要多长时间才能到达终点。
2.输入
第一行三个数k,n,m(k,n,m<=100)。 接下来k个图,两个图之间用一个空行隔开,每个图有n行,每行m个字符,字符含义如下:
‘#’ – 该位置为墙或者障碍。
‘.’ – 该位置可以正常行走。
‘T’ – 该位置有一传送点。
‘t’ – 从上图传送来的位置。
‘S’ – Teutonic Knight的起始位置。‘S’仅有一个。
‘E’ – 出口。‘E’仅有一个。
3.输出
仅一行,输出到达终点的最少时间。 如不能离开,输出“Trapped Maze!!!”。
4.样例输入
3 5 6
##.S#.
##.###
##…
.##.#.
##…#T
##.t…
##.##.
##.#…
T.#…#
#…##
###t##
##…#E
#…##.
#.##…
#…#
5.输出
33
代码展示
import java.util.AbstractMap;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
class Main {
static int n,a,b,x,y,X,Y;
static final int N = 110;
static char[][] s = new char[N][N];
static int [][] t = new int[N][N];
static Queue<AbstractMap.SimpleEntry<Integer,Integer>> queue = new ArrayDeque<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a = sc.nextInt(); //a 行
b = sc.nextInt(); // b 列
//读入每行字符串
for (int i = 0,j = 0; i < n * a ; i++,j++) {
s[i] = sc.next().toCharArray();
}
//定义到达每个点的距离 t[i][j],当 t[i][j] = -1 代表其未被访问过
for (int i = 0; i < n * a + n -1; i++) {
for (int j = 0; j < b; j++) {
t[i][j] = -1;
}
}
//找到起点(x,y) && 终点(X,Y)
for (int i = 0; i < n * a + n - 1; i++) {
for (int j = 0; j < b; j++) {
if (s[i][j] == 'S')
{
bfs(x,y);
}
}
public static void bfs(int x,int y)
{
//将起点放到队列中
queue.add(new AbstractMap.SimpleEntry<>(x,y));
//给定该点已经访问,但由于是起点,需要将其置为 0 而不是 -1
t[x][y] = 0;
s[x][y] = '#';
//定义偏移量
int [] dx = {-1,0,1,0};
int [] dy = {0,1,0,-1};
//存放结果
while (!queue.isEmpty())
{
//取出队头元素 -->其为上一个点存放的坐标(sx,sy),和由起点到达该点的距离t[sx][sy]
AbstractMap.SimpleEntry<Integer, Integer> remove = queue.remove();
int sx, sy;
//判定4个点是否有可行点,满足则加入到队列中去,不满足则不加
for (int i = 0; i < 4; i++)
{
sx = dx[i] + remove.getKey();
sy = dy[i] + remove.getValue();
//若该点未走过,满足要求下一共出现3中可能
/*宽搜的前提下,由于是第一次到达某点(sx,sy),t[sx][sy]即为由起点到达该点的最短距离*/
if (sx >= 0 && sx < n * a && sy >= 0 && sy < b && s[sx][sy] !='#' && t[sx][sy] == -1)
{
//1.若是 '.' --> 继续走
if (s[sx][sy] == '.')
{
t[sx][sy] = t[remove.getKey()][remove.getValue()] + 1;
s[sx][sy] = '#';
queue.add(new AbstractMap.SimpleEntry<>(sx,sy));
}
//2.若是 ’T‘ -->传送到下个点继续走
if (s[sx][sy] == 'T')
{
s[sx][sy] = '#';
f : for (int j = a; j < n * a; j++)
{
for (int k = 0; k < b; k++)
{
if (s[j][k] == 't')
{
t[j][k] = t[remove.getKey()][remove.getValue()] + 1;
s[j][k] = '#';
queue.add(new AbstractMap.SimpleEntry<>(j,k));
break f;
}
}
}
}
//3.走到终点停止
if (s[sx][sy] == 'E')
{
t[sx][sy] = t[remove.getKey()][remove.getValue()] + 1;
queue.add(new AbstractMap.SimpleEntry<>(sx,sy));
System.out.println(t[sx][sy]);
return;
}
}
}
if (queue.isEmpty()){
System.out.println("Trapped Maze!!!");
return;
}
}
}
}
6.附上本题代码,一个板子套的!
1. 本题中格外注意,全局变量queue随着每一次新的输入会重新来过,需要使用到clear()方法!!
import java.util.AbstractMap;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int N = 210;
static int a,b;
static char [][] s = new char[N][N];
static int [][] k = new int[N][N];
static Queue<AbstractMap.SimpleEntry<Integer,Integer>> queue =new ArrayDeque<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-->0)
{
a = sc.nextInt();
b = sc.nextInt();
for (int i = 0; i < a; i++) {
s[i] = sc.next().toCharArray();
}
for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
k[i][j] = -1;
}
}
f:for (int i = 0; i < a; i++) {
for (int j = 0; j < b; j++) {
if (s[i][j] == 'S')
{
bfs(i,j);
break f;
}
}
}
}
}
private static void bfs(int x,int y)
{
int [] dx = {-1, 0, 1, 0};
int [] dy = {0, 1, 0, -1};
queue.add(new AbstractMap.SimpleEntry<>(x,y));
s[x][y] = '#';
k[x][y] = 0;
while (!queue.isEmpty())
{
AbstractMap.SimpleEntry<Integer, Integer> remove = queue.remove();
int sx,sy;
for (int i = 0; i < 4; i++) {
sx = dx[i] + remove.getKey();
sy = dy[i] + remove.getValue();
if (sx >= 0 && sx < a && sy >=0 && sy < b && s[sx][sy] !='#' && k[sx][sy] == -1) {
if (s[sx][sy] == '.')
{
k[sx][sy] = k[remove.getKey()][remove.getValue()] + 1;
s[sx][sy] = '#';
queue.add(new AbstractMap.SimpleEntry<>(sx, sy));
}
if (s[sx][sy] == 'E')
{
k[sx][sy] = k[remove.getKey()][remove.getValue()] + 1;
queue.add(new AbstractMap.SimpleEntry<>(sx,sy));
System.out.println(k[sx][sy]);
queue.clear();
return;
}
}
}
if (queue.isEmpty()){
System.out.println("oop!");
queue.clear();
return;
}
}
}
}
学费了