[PHP] 蓝桥杯 BFS 战城

时限： 1000MS 
 
 内存限制： 65536K

我们正在讨论的是该游戏的简单版本。给定一张仅包含空白区域，河流，钢制墙和砖墙的地图。您的任务是假设没有敌人会打扰您，请尽快获得奖金（请参见下图）。

您的坦克无法穿过河流或墙壁，但可以通过射击破坏砖墙。撞到砖墙时，砖墙会变成空的空间，但是，如果击中钢墙，则不会损坏砖墙。在每个回合中，您可以选择移至相邻的（4个方向，而不是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[map.length][map[0].length];// 储存访问状态的矩阵
static int[][] step = new int[map.length][map[0].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[0].length; j++) {
// 查找起点，并在起点搜索
if (map[i][j] == '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[k];
int ny = ty + dy[k];
if (nx >= 0 && ny >= 0 && nx < map.length && ny < map[0].length
&& map[nx][ny] != 'S' && map[nx][ny] != 'R'
&& !check[nx][ny]) {
if (map[nx][ny] == 'E') {
// 空地，走一个回合
step[nx][ny] = step[tx][ty] + 1;
} else if (map[nx][ny] == 'B') {
// 砖墙，发一发子弹-走，两个回合
step[nx][ny] = step[tx][ty] + 2;
} else if (map[nx][ny] == 'T') {
// 奖励，吃到奖励需要往前走一个回合
step[nx][ny] = step[tx][ty] + 1;
min = Math.min(step[nx][ny], min);
}
// 标记访问
check[nx][ny] = true;// 将新的坐标标记访问
// 进行递归搜索
bfs(nx, ny);
// 回溯
check[nx][ny] = false;// 将坐标回溯回未访问状态
}
}
}
}