【华为OD-E卷 - 战场索敌 100分（python、java、c++、js、c）】

题目

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

输入描述

• 第一行输入为N,M,K；

N表示地图的行数，M表示地图的列数， K表示目标敌人数量 N，M<=100 之后为一个NxM大小的字符数组

输出描述

• 敌人数小于K的区域数量

用例

用例一：

输入：

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

• 1
• 2
• 3
• 4

输出：

1

• 1

python解法

• 解题思路：
• 这段代码的目标是统计满足以下条件的连通区域的数量：

每个连通区域由相邻的非障碍物（即不是 #）的单元格组成。
每个连通区域中包含的特殊单元格 E 的数量少于给定的阈值 k。
主要思路：

初始化：
读取输入构建网格 grid。
使用二维布尔数组 seen 跟踪是否访问过某个单元格。
深度优先搜索 (DFS)：
从未访问过的非障碍物单元格开始，使用 DFS 遍历该单元格所在的整个连通区域。
统计连通区域中特殊单元格 E 的数量。
条件判断：
如果某个连通区域中 E 的数量小于 k，将其计入结果。
结果输出：
输出满足条件的连通区域的总数量

# 读取输入
n, m, k = map(int, input().split())  # n: 行数, m: 列数, k: 特殊单元格数量阈值
grid = [input() for _ in range(n)]   # 读取网格，每行是一个字符串
seen = [[False] * m for _ in range(n)]  # 初始化访问标记数组，所有单元格未访问

# 深度优先搜索 (DFS) 函数，用于遍历连通区域并统计 'E' 的数量
def dfs(x, y):
    count = 1 if grid[x][y] == 'E' else 0  # 如果当前单元格是 'E'，初始计数为 1，否则为 0
    stack = [(x, y)]  # 使用栈实现 DFS，初始栈中包含当前单元格
    while stack:
        cx, cy = stack.pop()  # 弹出栈顶单元格
        # 遍历当前单元格的四个相邻单元格
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy  # 相邻单元格坐标
            # 检查相邻单元格是否在网格范围内、未访问过、且不是障碍物
            if 0 <= nx < n and 0 <= ny < m and not seen[nx][ny] and grid[nx][ny] != '#':
                seen[nx][ny] = True  # 标记相邻单元格为已访问
                stack.append((nx, ny))  # 将相邻单元格加入栈
                if grid[nx][ny] == 'E':  # 如果是特殊单元格 'E'，计数加 1
                    count += 1
    return count  # 返回连通区域中 'E' 的数量

result = 0  # 记录满足条件的连通区域数量
# 遍历整个网格，查找未访问过的非障碍物单元格
for i in range(n):
    for j in range(m):
        if not seen[i][j] and grid[i][j] != '#':  # 未访问且不是障碍物
            seen[i][j] = True  # 标记当前单元格为已访问
            # 使用 DFS 遍历该连通区域，统计 'E' 的数量
            if dfs(i, j) < k:  # 如果 'E' 的数量小于阈值 k
                result += 1  # 满足条件的连通区域计数加 1

# 输出结果
print(result)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35

java解法

• 解题思路
• 这段代码实现了在一个二维网格中查找满足以下条件的连通区域的数量：

每个连通区域是由相邻的非障碍物（即不是 #）组成。
连通区域中包含的特殊单元格 E 的数量小于目标值 target。
程序采用广度优先搜索（BFS）算法进行连通区域的遍历，具体步骤如下：

输入解析与初始化：

从输入中读取网格的维度、目标值 target 以及网格本身。
初始化布尔数组 marked，用来跟踪哪些单元格已访问。
区域查找与判断：

遍历网格中的每个单元格：
如果当前单元格未被访问且不是障碍物，使用 BFS 遍历该连通区域。
统计连通区域中 E 的数量，如果小于 target，则将该区域计入结果。
BFS 遍历实现：

使用队列保存当前连通区域的单元格。
遍历单元格的上下左右相邻单元格，如果符合条件（未访问且不是障碍物），将其加入队列并标记为已访问。
统计当前连通区域内 E 的数量。
结果输出：

返回满足条件的连通区域数量

import java.util.*;

public class Main {
    static int rows; // 网格的行数
    static int cols; // 网格的列数
    static int target; // 连通区域中 'E' 的数量阈值
    static char[][] grid; // 存储网格
    static boolean[][] marked; // 标记数组，用于记录单元格是否访问过

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

        // 读取输入的行数、列数和目标值
        int[] dimensions = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        rows = dimensions[0];
        cols = dimensions[1];
        target = dimensions[2];

        // 初始化标记数组和网格
        marked = new boolean[rows][cols];
        grid = new char[rows][];
        for (int i = 0; i < rows; i++) {
            grid[i] = scanner.nextLine().toCharArray(); // 读取每一行的网格数据
        }

        // 输出满足条件的连通区域数量
        System.out.println(countValidRegions());
    }

    // 统计满足条件的连通区域数量
    public static int countValidRegions() {
        int result = 0; // 计数器，用于记录满足条件的连通区域数量

        // 遍历整个网格
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果当前单元格未被访问且不是障碍物
                if (!marked[i][j] && grid[i][j] != '#') {
                    // 使用 BFS 遍历该连通区域，如果 'E' 的数量小于目标值，计入结果
                    if (exploreArea(i, j) < target) {
                        result++;
                    }
                }
            }
        }

        return result; // 返回满足条件的连通区域数量
    }

    // 定义方向数组，用于简化上下左右相邻单元格的访问
    static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 使用 BFS 遍历连通区域，并返回其中 'E' 的数量
    public static int exploreArea(int x, int y) {
        int enemyCount = 0; // 记录当前连通区域中 'E' 的数量

        marked[x][y] = true; // 标记起始单元格为已访问

        // 如果起始单元格是 'E'，计数加 1
        if (grid[x][y] == 'E') {
            enemyCount++;
        }

        // 初始化队列用于 BFS
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});

        // BFS 遍历
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 取出队列中的当前单元格
            int curX = current[0];
            int curY = current[1];

            // 遍历当前单元格的四个相邻单元格
            for (int[] dir : directions) {
                int newX = curX + dir[0];
                int newY = curY + dir[1];

                // 检查相邻单元格是否在网格范围内、未访问过、且不是障碍物
                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && !marked[newX][newY] && grid[newX][newY] != '#') {
                    marked[newX][newY] = true; // 标记相邻单元格为已访问

                    // 如果是 'E'，计数加 1
                    if (grid[newX][newY] == 'E') {
                        enemyCount++;
                    }

                    queue.offer(new int[]{newX, newY}); // 将相邻单元格加入队列
                }
            }
        }

        return enemyCount; // 返回当前连通区域中 'E' 的数量
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96

C++解法

• 解题思路
• 这段代码解决的问题是：在一个二维战场网格中，统计所有连通区域（由非障碍物 . 和 E 构成）的数量，其中每个连通区域包含的敌人 E 的数量小于指定阈值 enemyLimit。

主要思路如下：

输入与初始化：

从输入中读取网格的大小、敌人数量限制 enemyLimit，以及战场布局。
初始化一个布尔数组 checked，用于记录哪些单元格已经被访问过。
深度优先搜索 (DFS)：

对每个未被访问的非障碍物单元格进行 DFS 遍历。
在遍历过程中，统计当前连通区域中敌人 E 的数量。
如果该连通区域的敌人数小于 enemyLimit，计入结果。
连通区域的遍历与判断：

遍历网格中的每个单元格，跳过已访问或障碍物的单元格。
对于符合条件的单元格，调用 DFS 遍历整个连通区域并进行统计。
输出结果：

返回满足条件的连通区域数量

#include 
#include 

using namespace std;

int rows, cols, enemyLimit; // 行数、列数和敌人数限制
vector<vector<char>> battlefield; // 二维网格，表示战场
vector<vector<bool>> checked; // 标记数组，记录单元格是否已访问

// 方向数组，用于简化上下左右相邻单元格的访问
int rowOffsets[] = { -1, 1, 0, 0 };
int colOffsets[] = { 0, 0, -1, 1 };

// 深度优先搜索 (DFS) 函数，返回连通区域内敌人数量
int dfs(int x, int y) {
    checked[x][y] = true; // 标记当前单元格为已访问
    int enemyCount = 0; // 当前连通区域内的敌人数

    if (battlefield[x][y] == 'E') {
        enemyCount++; // 如果当前单元格是敌人，计数加 1
    }

    // 遍历当前单元格的四个相邻单元格
    for (int d = 0; d < 4; d++) {
        int newX = x + rowOffsets[d];
        int newY = y + colOffsets[d];

        // 检查相邻单元格是否在网格范围内、未访问过且不是障碍物
        if (newX >= 0 && newX < rows && newY >= 0 && newY < cols
            && !checked[newX][newY] && battlefield[newX][newY] != '#') {
            enemyCount += dfs(newX, newY); // 递归计算相邻单元格中的敌人数
        }
    }

    return enemyCount; // 返回当前连通区域中的敌人数
}

// 计算满足条件的连通区域数量
int calculateRegions() {
    int regionsBelowLimit = 0; // 记录满足条件的连通区域数量

    // 遍历网格中的每个单元格
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            // 如果当前单元格未访问且是非障碍物
            if (!checked[i][j] && battlefield[i][j] == '.') {
                // 使用 DFS 遍历连通区域并统计敌人数
                if (dfs(i, j) < enemyLimit) {
                    regionsBelowLimit++; // 如果敌人数小于限制，计入结果
                }
            }
        }
    }

    return regionsBelowLimit; // 返回满足条件的连通区域数量
}

int main() {
    // 读取网格大小和敌人数限制
    cin >> rows >> cols >> enemyLimit;
    cin.ignore(); // 忽略换行符

    // 初始化战场和标记数组
    battlefield.resize(rows, vector<char>(cols));
    checked.resize(rows, vector<bool>(cols, false));

    // 读取网格内容
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            cin >> battlefield[i][j];
        }
    }

    // 计算并输出满足条件的连通区域数量
    cout << calculateRegions() << endl;
    return 0;
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78

C解法

• 解题思路

更新中

• 1

JS解法

• 解题思路

• 这段代码解决的问题是：在一个二维网格中，找到所有满足以下条件的连通区域的数量：

连通区域由非障碍物 . 或 E 构成；
连通区域中包含的敌人 E 的数量小于限制值 limit。
代码采用 广度优先搜索 (BFS) 方法进行区域探索，以下是具体步骤：

输入解析与初始化：

从输入读取网格的行数、列数、敌人数量限制值 limit 和网格内容。
初始化一个布尔数组 visited，用来记录哪些单元格已经访问过。
连通区域查找与判断：

遍历网格的每个单元格：
如果当前单元格未被访问且不是障碍物，使用 BFS 遍历它所在的连通区域。
在 BFS 过程中统计当前区域内的敌人 E 的数量。
如果敌人数小于 limit，将该区域计入结果。
BFS 实现：

使用队列保存当前连通区域的单元格。
对于每个单元格，检查其上下左右四个方向的相邻单元格是否满足条件（未访问且不是障碍物），如果满足，则加入队列。
在遍历的同时统计敌人 E 的数量。
输出结果：

返回满足条件的连通区域数量

const readline = require("readline");

// 设置输入输出流
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let grid, visited;
let rows, cols, limit;

const data = []; // 用于存储输入数据

rl.on("line", (line) => {
  data.push(line); // 读取每一行输入

  // 第一行解析网格大小和敌人限制值
  if (data.length === 1) {
    [rows, cols, limit] = data[0].split(" ").map(Number);
  }

  // 读取完整的网格数据后，开始计算结果
  if (data.length === rows + 1) {
    grid = data.slice(1); // 网格数据
    visited = Array.from({ length: rows }, () => Array(cols).fill(false)); // 初始化访问标记数组

    // 输出满足条件的连通区域数量
    console.log(findAreas());

    // 清空数据，准备处理下一组输入
    data.length = 0;
  }
});

// 统计满足条件的连通区域数量
function findAreas() {
  let count = 0; // 用于记录满足条件的区域数量

  // 遍历整个网格
  for (let x = 0; x < rows; x++) {
    for (let y = 0; y < cols; y++) {
      // 如果当前单元格未访问且不是障碍物
      if (!visited[x][y] && grid[x][y] !== '#') {
        const enemies = explore(x, y); // 使用 BFS 探索连通区域并统计敌人数
        if (enemies < limit) count++; // 如果敌人数小于限制，计入结果
      }
    }
  }

  return count; // 返回满足条件的连通区域数量
}

// 定义方向数组，用于简化上下左右的相邻单元格访问
const directions = [
  [-1, 0], [1, 0], [0, -1], [0, 1]
];

// 使用 BFS 探索连通区域，并返回区域内敌人的数量
function explore(x, y) {
  let enemyCount = 0; // 当前连通区域中的敌人数
  if (grid[x][y] === 'E') enemyCount++; // 如果起始单元格是敌人，计数加 1

  const queue = [[x, y]]; // 初始化队列
  visited[x][y] = true; // 标记起始单元格为已访问

  // BFS 遍历
  while (queue.length) {
    const [curX, curY] = queue.shift(); // 取出队列中的当前单元格

    // 遍历当前单元格的四个相邻单元格
    for (const [dx, dy] of directions) {
      const newX = curX + dx;
      const newY = curY + dy;

      // 检查相邻单元格是否在网格范围内、未访问且不是障碍物
      if (
        newX >= 0 && newX < rows &&
        newY >= 0 && newY < cols &&
        !visited[newX][newY] &&
        grid[newX][newY] !== '#'
      ) {
        if (grid[newX][newY] === 'E') enemyCount++; // 如果是敌人，计数加 1
        visited[newX][newY] = true; // 标记为已访问
        queue.push([newX, newY]); // 将相邻单元格加入队列
      }
    }
  }

  return enemyCount; // 返回当前连通区域的敌人数
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏