华为OD机试真题【士兵突击】

落日映苍穹つ 2023-10-10 17:54 45阅读 0赞

#### 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）[西天取经][Link 1]  
（2）[上班之路][Link 2]

[Link 1]: https://blog.csdn.net/weixin_43763430/article/details/130716731
[Link 2]: https://blog.csdn.net/weixin_43763430/article/details/130695583