华为OD机试真题---战场索敌

华为OD机试真题“战场索敌”是一道考察算法和数据结构应用能力的题目。以下是对该题目的详细解析：

一、题目描述

有一个大小是N×M的战场地图，被墙壁’#‘分隔成大小不同的区域。上下左右四个方向相邻的空地’.‘属于同一个区域，只有空地上可能存在敌人’E’。请求出地图上总共有多少区域里的敌人数小于K。

二、输入描述

第一行输入为N，M，K；N表示地图的行数，M表示地图的列数，K表示目标敌人数量。N，M≤100。之后为一个N×M大小的字符数组。

三、输出描述

输出敌人数小于K的区域数量。

四、示例1

输入

3 5 2
..#EE
E.#E.
###..
1234

输出

1

说明

地图被墙壁分为两个区域，左边区域有1个敌人，右边区域有3个敌人，符合条件的区域数量是1

五、解题思路

1. 理解题目：

   • 首先，明确题目要求统计的是敌人数小于K的区域数量。
   • 地图被墙壁’#‘分隔成不同的区域，每个区域内的空地’.‘是连通的，且只有空地上可能存在敌人’E’。

2. 确定算法：

   • 由于需要遍历地图并统计每个区域内的敌人数量，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来遍历每个区域。
   • 在遍历过程中，使用一个计数器来统计每个区域内的敌人数量，并判断该数量是否小于K。

3. 实现步骤：

   • 初始化一个二维布尔数组visited，用于标记地图中的每个位置是否已经被访问过。
   • 定义一个DFS函数，该函数接受当前位置(i, j)和计数器count作为参数。
   • 在DFS函数中，首先检查当前位置是否越界、是否已被访问过或是否是墙壁’#‘。如果不满足这些条件，则将其标记为已访问，并根据当前位置的值判断是否为敌人’E’（如果是，则count加1）。
   • 然后，递归地调用DFS函数来访问当前位置的上下左右四个相邻位置。
   • 在遍历完一个区域后，检查该区域内的敌人数量是否小于K，如果是，则结果加1。
   • 最后，输出结果。

六、代码示例（Python）

def battlefield_enemy_count(N, M, K, grid):
    """
    计算战场中敌人数目小于K的区域数量。
    
    参数:
    N: 战场网格的行数
    M: 战场网格的列数
    K: 敌人数目的阈值
    grid: 表示战场网格的二维列表，其中 'E' 表示敌人，'.' 表示空地，'#' 表示障碍物
    
    返回:
    敌人数目小于K的区域数量
    """
    
    def dfs(i, j, count):
        """
        深度优先搜索函数，用于计算从网格(i, j)开始的区域内的敌人数目。
        
        参数:
        i: 网格的行索引
        j: 网格的列索引
        count: 当前区域内已计算的敌人数目
        
        返回:
        当前区域内的敌人数目
        """
        # 检查索引是否越界，当前网格是否为障碍物，或者已经访问过
        if i < 0 or i >= N or j < 0 or j >= M or grid[i][j] == '#' or visited[i][j]:
            return
        # 标记当前网格为已访问
        visited[i][j] = True
        # 如果当前网格有敌人，增加计数
        if grid[i][j] == 'E':
            count += 1
        # 定义四个方向，分别表示右、左、下、上
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        # 遍历四个方向，进行深度优先搜索
        for dx, dy in directions:
            dfs(i + dx, j + dy, count)
        # 返回当前区域内的敌人数目
        return count

    # 初始化visited二维列表，用于标记网格是否被访问过
    visited = [[False] * M for _ in range(N)]
    # 初始化结果变量，用于记录敌人数目小于K的区域数量
    result = 0
    # 遍历战场网格的每一个位置
    for i in range(N):
        for j in range(M):
            # 如果当前网格不是障碍物且未被访问过
            if grid[i][j] != '#' and not visited[i][j]:
                # 计算从当前网格开始的区域内的敌人数目
                enemy_count = dfs(i, j, 0)
                # 如果敌人数目小于K，增加结果变量
                if enemy_count < K:
                    result += 1
    # 返回敌人数目小于K的区域数量
    return result


# 示例输入
N = 3
M = 5
K = 2
grid = [
    "..#EE",
    "E.#E.",
    "#..E#"
]

# 调用函数并输出结果
print(battlefield_enemy_count(N, M, K, grid))  # 输出: 1

七、代码示例（java）

以下是使用Java实现的“战场索敌”问题解决方案。这个实现利用了深度优先搜索（DFS）算法来遍历战场地图，并统计每个连通区域中的敌人数量。

import java.util.Scanner;

public class BattlefieldEnemyCount {

    // 四个方向的行列偏移量，分别代表右、左、下、上
    private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int K = scanner.nextInt();
        scanner.nextLine(); // 读取换行符

        char[][] grid = new char[N][M];
        for (int i = 0; i < N; i++) {
            grid[i] = scanner.nextLine().toCharArray();
        }

        // 调用函数计算结果
        int result = countRegionsWithLessThanKEnemies(N, M, K, grid);

        // 输出结果
        System.out.println(result);
    }

    /**
     * 计算地图中敌人数目小于K的区域数量
     * 
     * @param N 地图的行数
     * @param M 地图的列数
     * @param K 敌人数目的阈值
     * @param grid 表示地图的二维字符数组，其中'#'表示障碍物，'E'表示敌人，'.'表示空地
     * @return 返回敌人数目小于K的区域数量
     */
    public static int countRegionsWithLessThanKEnemies(int N, int M, int K, char[][] grid) {
        // 初始化访问标记数组
        boolean[][] visited = new boolean[N][M];
        // 初始化区域计数为0
        int regionCount = 0;
    
        // 遍历地图中的每个位置
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 如果当前位置是空地且未被访问过，则开始DFS搜索
                if (grid[i][j] != '#' && !visited[i][j]) {
                    // dfs函数返回从当前位置开始的区域中的敌人数量
                    int enemyCount = dfs(i, j, grid, visited);
                    // 如果敌人数量小于K，则区域计数加1
                    if (enemyCount < K) {
                        regionCount++;
                    }
                }
            }
        }
    
        // 返回敌人数目小于K的区域数量
        return regionCount;
    }

    /* 深度优先搜索函数，用于计算从(i, j)位置出发能遇到的敌人数量
    ** 参数i, j表示当前位置，grid表示地图，visited表示访问状态数组
     返回值为从当前位置出发遇到的敌人总数
    * **/
    private static int dfs(int i, int j, char[][] grid, boolean[][] visited) {
        int enemyCount = 0;
    
        // 检查边界条件和访问状态
        // 如果当前位置越界、已被访问或遇到障碍物('#')，则返回0
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || visited[i][j] || grid[i][j] == '#') {
            return enemyCount;
        }
    
        // 标记当前位置为已访问
        visited[i][j] = true;
    
        // 如果当前位置是敌人，则敌人计数加1
        if (grid[i][j] == 'E') {
            enemyCount++;
        }
    
        // 对四个方向进行递归搜索
        // DIRECTIONS是一个预定义的数组，包含四个方向的行和列增量
        for (int[] direction : DIRECTIONS) {
            int newRow = i + direction[0];
            int newCol = j + direction[1];
            enemyCount += dfs(newRow, newCol, grid, visited);
        }
    
        // 返回从当前位置出发遇到的敌人总数
        return enemyCount;
    }
}

代码说明：

1. 输入处理：

   • 使用Scanner类读取输入的行数N、列数M、目标敌人数量K以及战场地图grid。

2. 主函数：

   • countRegionsWithLessThanKEnemies函数负责遍历整个地图，并对每个未被访问过的空地位置调用DFS函数。
   • 如果DFS返回的敌人数量小于K，则增加区域计数。

3. DFS函数：

   • dfs函数执行深度优先搜索，递归地访问当前位置的四个相邻位置。
   • 使用visited数组来跟踪已访问的位置，以避免重复访问。
   • 如果当前位置是敌人，则增加敌人计数。

4. 输出：

   • 最后，输出满足条件的区域数量。

你可以将上述代码复制到你的Java开发环境中进行编译和运行，并根据需要调整输入部分来测试不同的战场地图。

八、详细运行示例解析：

输入：

3 5 2
..#EE
E.#E.
###..
1234

输入解析：

• 3 5 2 表示地图有3行5列，且我们关心敌人数量小于2的区域。
• 接下来的三行是地图：

  ..#EE
  E.#E.
  ###..
  

  其中，. 表示空地，# 表示墙壁（障碍物），E 表示敌人。

代码运行流程：

1. 初始化：

   • Scanner 用于读取输入。
   • grid 二维字符数组用于存储地图。
   • visited 二维布尔数组用于标记哪些位置已被访问。
   • regionCount 用于记录敌人数量小于2的区域数量。

2. 读取输入：

   • 使用Scanner读取行数N、列数M和阈值K。
   • 读取地图并存储在grid中。

3. 遍历地图：

   • 双重循环遍历地图的每个位置。
   • 对于每个未访问过的空地位置，调用dfs函数计算该位置所在区域的敌人数量。

4. 深度优先搜索（DFS）：

   • 从当前位置(i, j)开始，递归地搜索四个方向。
   • 使用visited数组避免重复访问。
   • 如果遇到敌人，增加enemyCount。
   • 递归调用dfs处理相邻位置。

5. 判断并计数：

   • 在遍历地图的过程中，如果某个区域的敌人数量小于K（即2），则regionCount加1。

6. 输出结果：

   • 打印regionCount，即敌人数量小于2的区域数量。

运行示例解析：

• 区域1（左上角..#EE中的..EE部分）：

  • 敌人数量：2
  • 不满足条件（敌人数量小于2），不计入regionCount。

• 区域2（中间E.#E.部分）：

  • 敌人数量：2
  • 不满足条件（敌人数量小于2），不计入regionCount。

• 区域3（由于墙壁分隔，###..中的..是一个独立的空地区域，但无敌人）：

  • 敌人数量：0
  • 满足条件（敌人数量小于2），regionCount加1。

输出结果：

1

因此，根据给定的输入和代码实现，输出结果为1，表示有一个区域的敌人数量小于2。这个区域是地图右下角的独立空地区域（无敌人）。

九、总结

华为OD机试真题“战场索敌”是一道考察算法和数据结构应用能力的题目。通过理解题目要求、确定算法和实现步骤，我们可以使用深度优先搜索（DFS）算法来遍历地图并统计每个区域内的敌人数量。最后，根据题目要求输出结果即可。