网站申请名称和域名贵州企业官网建设

当前位置： 首页 > news >正文

网站申请名称和域名,贵州企业官网建设,商城网站需要注意事项,wordpress分类树形目录华为OD机试真题“战场索敌”是一道考察算法和数据结构应用能力的题目。以下是对该题目的详细解析#xff1a; 一、题目描述 有一个大小是NM的战场地图#xff0c;被墙壁’#‘分隔成大小不同的区域。上下左右四个方向相邻的空地’.‘属于同一个区域#xff0c;只有空地上可…华为OD机试真题“战场索敌”是一道考察算法和数据结构应用能力的题目。以下是对该题目的详细解析 一、题目描述 有一个大小是N×M的战场地图被墙壁’#‘分隔成大小不同的区域。上下左右四个方向相邻的空地’.‘属于同一个区域只有空地上可能存在敌人’E’。请求出地图上总共有多少区域里的敌人数小于K。 二、输入描述 第一行输入为NMKN表示地图的行数M表示地图的列数K表示目标敌人数量。NM≤100。之后为一个N×M大小的字符数组。 三、输出描述 输出敌人数小于K的区域数量。 四、示例1 输入 3 5 2 ..#EE E.#E. ###.. 1234输出 1说明 地图被墙壁分为两个区域左边区域有1个敌人右边区域有3个敌人符合条件的区域数量是1 五、解题思路 理解题目 首先明确题目要求统计的是敌人数小于K的区域数量。地图被墙壁’#‘分隔成不同的区域每个区域内的空地’.‘是连通的且只有空地上可能存在敌人’E’。 确定算法 由于需要遍历地图并统计每个区域内的敌人数量可以使用深度优先搜索DFS或广度优先搜索BFS算法来遍历每个区域。在遍历过程中使用一个计数器来统计每个区域内的敌人数量并判断该数量是否小于K。 实现步骤 初始化一个二维布尔数组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];// 初始化区域计数为0int 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则区域计数加1if (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;// 检查边界条件和访问状态// 如果当前位置越界、已被访问或遇到障碍物(#)则返回0if (i 0 || i grid.length || j 0 || j grid[0].length || visited[i][j] || grid[i][j] #) {return enemyCount;}// 标记当前位置为已访问visited[i][j] true;// 如果当前位置是敌人则敌人计数加1if (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;} }代码说明 输入处理 使用Scanner类读取输入的行数N、列数M、目标敌人数量K以及战场地图grid。 主函数 countRegionsWithLessThanKEnemies函数负责遍历整个地图并对每个未被访问过的空地位置调用DFS函数。如果DFS返回的敌人数量小于K则增加区域计数。 DFS函数 dfs函数执行深度优先搜索递归地访问当前位置的四个相邻位置。使用visited数组来跟踪已访问的位置以避免重复访问。如果当前位置是敌人则增加敌人计数。 输出 最后输出满足条件的区域数量。
你可以将上述代码复制到你的Java开发环境中进行编译和运行并根据需要调整输入部分来测试不同的战场地图。 八、详细运行示例解析 输入 3 5 2 ..#EE E.#E. ###.. 1234输入解析 3 5 2 表示地图有3行5列且我们关心敌人数量小于2的区域。接下来的三行是地图..#EE E.#E. ###..其中. 表示空地# 表示墙壁障碍物E 表示敌人。 代码运行流程 初始化 Scanner 用于读取输入。grid 二维字符数组用于存储地图。visited 二维布尔数组用于标记哪些位置已被访问。regionCount 用于记录敌人数量小于2的区域数量。 读取输入 使用Scanner读取行数N、列数M和阈值K。读取地图并存储在grid中。 遍历地图 双重循环遍历地图的每个位置。对于每个未访问过的空地位置调用dfs函数计算该位置所在区域的敌人数量。 深度优先搜索DFS 从当前位置(i, j)开始递归地搜索四个方向。使用visited数组避免重复访问。如果遇到敌人增加enemyCount。递归调用dfs处理相邻位置。 判断并计数 在遍历地图的过程中如果某个区域的敌人数量小于K即2则regionCount加1。 输出结果 打印regionCount即敌人数量小于2的区域数量。
运行示例解析 区域1左上角..#EE中的..EE部分 敌人数量2不满足条件敌人数量小于2不计入regionCount。 区域2中间E.#E.部分 敌人数量2不满足条件敌人数量小于2不计入regionCount。 区域3由于墙壁分隔###..中的..是一个独立的空地区域但无敌人 敌人数量0满足条件敌人数量小于2regionCount加1。
输出结果 1因此根据给定的输入和代码实现输出结果为1表示有一个区域的敌人数量小于2。这个区域是地图右下角的独立空地区域无敌人。 九、总结 华为OD机试真题“战场索敌”是一道考察算法和数据结构应用能力的题目。通过理解题目要求、确定算法和实现步骤我们可以使用深度优先搜索DFS算法来遍历地图并统计每个区域内的敌人数量。最后根据题目要求输出结果即可。