1、题目描述

【士兵突击】
在一个 M ∗ N 的街区中，有一个士兵 S 和一个敌人 E ， 标识 X 为无法通过的街区，标识 B 为可以通过的街区；
士兵在一个单位时间内可以从一个街区移动到相邻的街区（土兵每次只能水平或者垂直方向移动一个街区）；
士兵每次改变方向时，需要额外花费个 单位的时间（士兵第一次移动个街区的时候，不用考虑其初始方向，即只需要一个单位时间即可到达相邻街区）。
计算士兵 S 最少需要多少时间才能到达 E 所在的街区。

【输入描述】
第一行为两个数字，标识街区的大小，M行，N列；（1<=M，N <= 1000，M、N不同时为1）
接下来M行，每行N个字母，字母S表示士兵所在街区，字母E表示敌人所在街区，字母X表示障碍，字母B表示可以经过的街区（只有一个S，一个E）

【输出描述】
最少需要的时间，当士兵S永远无法到达敌人E所在街区时，输出-1

【示例一】
输入：
6 6
SBBBBB
BXXXXB
BBXBBB
XBBXXB
BXBBXB
BBXBEB

输出 ： 13
说明：
当士兵S沿左侧路线时，需要经过9个街区，改变方向7次，共16单位时间；
当士兵S沿右侧路线时，需要经过11个街区，改变方向2次，共13单位时间；
所以最少需要的时间为13

2、解题思路

该题与上班之路思路一致，先遍历找到士兵S的位置，再向四个方向依次遍历，计算到达敌人E街区所花费的时间，统计最少时间的路线。

3、参考代码

import java.util.Scanner;/*** @Author* @Date 2023/5/6 23:46*/
public class 士兵突击 {static int[][] dir = new int[][] {{1, 0 ,1}, {-1, 0, 2}, {0, 1, 3}, {0, -1, 4}};static int res = Integer.MAX_VALUE;public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int m = in.nextInt();int n = in.nextInt();in.nextLine();char[][] chars = new char[m][n];for (int i = 0; i < m; i++) {chars[i] = in.nextLine().toCharArray();}int si = 0;int sj = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (chars[i][j] == 'S') {si = i;sj = j;break;}}}for (int i = 0; i < dir.length; i++) {boolean[][] used = new boolean[m][n];used[si][sj] = true;dfs(chars, si + dir[i][0], sj + dir[i][1], dir[i][2], 1, used);}if (res == Integer.MAX_VALUE) {System.out.println(-1);} else {System.out.println(res);}}}public static void dfs(char[][] chars, int i, int j, int direction, int count, boolean[][] user) {int m = chars.length;int n = chars[0].length;if (i < 0 || i >= m || j < 0 || j >= n || chars[i][j] == 'X') {return;}// 到达E 目的地if (chars[i][j] == 'E') {res = Math.min(res, count);return;}user[i][j] = true;// 分别遍历四个方向for (int k = 0; k < dir.length; k++) {int newI = i + dir[k][0];int newJ = j + dir[k][1];if (newI < 0 || newI >= m || newJ < 0 || newJ >= n ||chars[newI][newJ] == 'X') {continue;}if (user[newI][newJ]) {continue;}if (dir[k][2] == direction) {  // 不改变方向dfs(chars, newI, newJ, dir[k][2], count + 1, user);} else {  // 改变方向dfs(chars, newI, newJ, dir[k][2], count + 2, user);}}user[i][j] = false;}
}

4、相似题目

（1）西天取经
（2）上班之路