蓝桥杯 BFS 战城
战城 时限： 1000MS内存限制： 65536K 描述我们中的许多人在童年时代就曾玩过“战斗之城”游戏，现在有些人（例如我）甚至经常在计算机上玩它。
我们正在讨论的是该游戏的简单版本。给定一张仅包含空白区域，河流，钢制墙和砖墙的地图。您的任务是假设没有敌人会打扰您，请尽快获得奖金（请参见下图）。
您的坦克无法穿过河流或墙壁，但可以通过射击破坏砖墙。撞到砖墙时，砖墙会变成空的空间，但是，如果击中钢墙，则不会损坏砖墙。在每个回合中，您可以选择移至相邻的（4个方向，而不是8个）空白空间，或在不移动的情况下向四个方向之一射击一发子弹。子弹将朝该方向前进，直到超出地图或撞到墙壁为止。如果子弹碰到了砖墙，则墙壁将消失（即，这时）。那么，给定地图的描述，坦克的位置和目标的位置，您至少要转多少回合能到达那里？
输入输入包含几个测试用例。每个测试用例的第一行包含两个整数M和N（2 <= M，N <= 300）。以下M行中的每行均包含N个大写字母，每个字母均是“ Y”（您），“ T”（目标），“ S”（钢壁），“ B”（砖壁）和“ R”（河流）和“ E”（空白）。“ Y”和“ T”都只出现一次。
输出如果无法到达目标，请输出“ -1”。
样本输入3 4
YBEB
EERE
SSTE
样本输出8
参考代码 package T4_战城;
public class Main {
static char[][] map = {
// {'Y','B','E','B'},
// {'E','E','R','E'},
// {'S','S','T','E'}
{ 'Y', 'E', 'E', 'E', 'E' }, { 'B', 'E', 'R', 'E', 'E' },
{ 'B', 'B', 'E', 'E', 'E' }, { 'B', 'S', 'E', 'E', 'E' },
{ 'B', 'T', 'E', 'E', 'E' } };
static int min = 100000;// 最小步数
static boolean[][] check = new boolean.length];// 储存访问状态的矩阵
static int[][] step = new int.length];// 储存运动步数的矩阵
// 坐标轴移动数组
static int[] dx = { 1, -1, 0, 0 };
static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map.length; j++) {
// 查找起点，并在起点搜索
if (map == 'Y') {
bfs(i, j);
}
}
}
System.out.println(min);
}
private static void bfs(int i, int j) {
int tx = i;
int ty = j;
// 根据移动方向，生成新的坐标
for (int k = 0; k < dx.length; k++) {
int nx = tx + dx;
int ny = ty + dy;
if (nx >= 0 && ny >= 0 && nx < map.length && ny < map.length
&& map != 'S' && map != 'R'
&& !check) {
if (map == 'E') {
// 空地，走一个回合
step = step + 1;
} else if (map == 'B') {
// 砖墙，发一发子弹-走，两个回合
step = step + 2;
} else if (map == 'T') {
// 奖励，吃到奖励需要往前走一个回合
step = step + 1;
min = Math.min(step, min);
}
// 标记访问
check = true;// 将新的坐标标记访问
// 进行递归搜索
bfs(nx, ny);
// 回溯
check = false;// 将坐标回溯回未访问状态
}
}
}
}
https://blog.51cto.com/u_15470300/4862799
页:
[1]