# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

from collections import deque

# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]

# 输入行数n，列数m，阈值k
n, m, k = map(int, input().split())
# 输入网格
grid = list()
for _ in range(n):
    grid.append(input())


# 答案变量，用于记录敌人个数大于k的的连通块的个数
ans = 0
# 用于检查的二维矩阵
# 0表示没检查过，1表示检查过了
check_list = [[0] * m for _ in range(n)]

# 最外层的大的双重循环，是用来找BFS的起始搜索位置的
for i in range(n):
    for j in range(m):
        # 找到一个"."或"E"，并且这个"."或"E"从未被搜索过：那么可以进行BFS的搜索
        if grid[i][j] != "#" and check_list[i][j] == 0:
            # BFS的过程
            q = deque()
            q.append([i, j])        # BFS的起始点
            check_list[i][j] = 1
            # 初始化当前连通块的敌人数目cur_num为0
            cur_num = 0
            while len(q) > 0:       # 当队列中还有元素时，持续地进行搜索
                qSize = len(q)
                for _ in range(qSize):
                    # 弹出队头元素，为当前点
                    x, y = q.popleft()
                    # 如果当前位置是敌人，则更新当前连通块的敌人数目cur_num
                    if grid[x][y] == "E":
                        cur_num += 1
                    for dx, dy in DIRECTIONS:
                        nxt_x, nxt_y = x+dx, y+dy
                        # 若下一个点要加入队列，应该满足以下三个条件：
                        # 1.没有越界
                        # 2.在grid中值为"."或"E"
                        # 3.尚未被检查过
                        if 0 <= nxt_x < n and 0 <= nxt_y < m:       # 越界判断
                            if grid[nxt_x][nxt_y] != "#" and check_list[nxt_x][nxt_y] == 0:
                                q.append([nxt_x, nxt_y])        # 入队
                                check_list[nxt_x][nxt_y] = 1    # 标记为已检查过

            # BFS搜索完成，如果cur_num小于k，更新ans
            if cur_num < k:
                ans += 1

print(ans)

Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    // Represent four directions as an array
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

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

        // Input the number of rows n, columns m, and the threshold k
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        // Input the grid
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = scanner.next().toCharArray();
        }

        // Answer variable to count the number of connected blocks with more than k enemies
        int ans = 0;

        // Two-dimensional matrix for checking
        // 0 means not checked, 1 means checked
        int[][] checkList = new int[n][m];

        // Outermost double loop is used to find BFS's starting search position
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // Find a "." or "E" and it has not been searched before: then BFS search can be performed
                if (grid[i][j] != '#' && checkList[i][j] == 0) {
                    // BFS process
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j}); // BFS starting point
                    checkList[i][j] = 1;
                    // Initialize the number of enemies in the current connected block curNum to 0
                    int curNum = 0;
                    while (!queue.isEmpty()) { // Continue searching as long as there are elements in the queue
                        int qSize = queue.size();
                        for (int q = 0; q < qSize; q++) {
                            // Dequeue the front element as the current point
                            int[] current = queue.poll();
                            int x = current[0];
                            int y = current[1];
                            // If the current position is an enemy, update curNum
                            if (grid[x][y] == 'E') {
                                curNum++;
                            }
                            for (int[] direction : DIRECTIONS) {
                                int nextX = x + direction[0];
                                int nextY = y + direction[1];
                                // If the next point can be added to the queue, it should satisfy three conditions:
                                // 1. Not out of bounds
                                // 2. The value in the grid is "." or "E"
                                // 3. Has not been checked yet
                                if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m &&
                                        (grid[nextX][nextY] != '#' && checkList[nextX][nextY] == 0)) {
                                    // Enqueue the next point
                                    queue.add(new int[]{nextX, nextY});
                                    // Mark it as checked
                                    checkList[nextX][nextY] = 1;
                                }
                            }
                        }
                    }
                    // BFS search is complete, if curNum is less than k, update ans
                    if (curNum < k) {
                        ans++;
                    }
                }
            }
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// Represent four directions as a vector of pairs
const vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // Input the grid
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    // Answer variable to count the number of connected blocks with more than k enemies
    int ans = 0;

    // Two-dimensional matrix for checking
    // 0 means not checked, 1 means checked
    vector<vector<int>> checkList(n, vector<int>(m, 0));

    // Outermost double loop is used to find BFS's starting search position
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Find a "." or "E" and it has not been searched before: then BFS search can be performed
            if (grid[i][j] != '#' && checkList[i][j] == 0) {
                // BFS process
                queue<pair<int, int>> q;
                q.push({i, j}); // BFS starting point
                checkList[i][j] = 1;
                // Initialize the number of enemies in the current connected block curNum to 0
                int curNum = 0;
                while (!q.empty()) { // Continue searching as long as there are elements in the queue
                    pair<int, int> current = q.front(); // Dequeue the front element as the current point
                    q.pop();
                    int x = current.first;
                    int y = current.second;
                    // If the current position is an enemy, update curNum
                    if (grid[x][y] == 'E') {
                        curNum++;
                    }
                    for (const auto& direction : DIRECTIONS) {
                        int nextX = x + direction.first;
                        int nextY = y + direction.second;
                        // If the next point can be added to the queue, it should satisfy three conditions:
                        // 1. Not out of bounds
                        // 2. The value in the grid is "." or "E"
                        // 3. Has not been checked yet
                        if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m &&
                            (grid[nextX][nextY] != '#' && checkList[nextX][nextY] == 0)) {
                            // Enqueue the next point
                            q.push({nextX, nextY});
                            // Mark it as checked
                            checkList[nextX][nextY] = 1;
                        }
                    }
                }
                // BFS search is complete, if curNum is less than k, update ans
                if (curNum < k) {
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000
#define QUEUE_SIZE (MAX_N * MAX_N)

// 四个方向数组
int DIRECTIONS[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
char grid[MAX_N][MAX_N];
int checkList[MAX_N][MAX_N];  // 检查矩阵
int queue[QUEUE_SIZE][2];  // BFS 队列
int front, rear;

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    // 输入网格
    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    int ans = 0;

    // 双重循环寻找BFS起始位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '#' && checkList[i][j] == 0) {
                front = rear = 0;
                queue[rear][0] = i;
                queue[rear++][1] = j;
                checkList[i][j] = 1;
                int curNum = 0;

                while (front < rear) {
                    int x = queue[front][0];
                    int y = queue[front++][1];
                    if (grid[x][y] == 'E') curNum++;

                    for (int d = 0; d < 4; d++) {
                        int nxtX = x + DIRECTIONS[d][0];
                        int nxtY = y + DIRECTIONS[d][1];
                        if (nxtX >= 0 && nxtX < n && nxtY >= 0 && nxtY < m) {
                            if (grid[nxtX][nxtY] != '#' && checkList[nxtX][nxtY] == 0) {
                                checkList[nxtX][nxtY] = 1;
                                queue[rear][0] = nxtX;
                                queue[rear++][1] = nxtY;
                            }
                        }
                    }
                }

                if (curNum < k) ans++;
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

Node JavaScript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const DIRECTIONS = [[0, 1], [1, 0], [-1, 0], [0, -1]];  // 表示四个方向的数组

let n, m, k;
let grid = [];

rl.on('line', (line) => {
    if (!n) {
        [n, m, k] = line.split(' ').map(Number);
    } else {
        grid.push(line);
        if (grid.length === n) rl.close();
    }
});

rl.on('close', () => {
    let ans = 0;
    let checkList = Array.from({ length: n }, () => Array(m).fill(0)); // 初始化检查矩阵

    // 双重循环，找到BFS的起始点
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (grid[i][j] !== '#' && checkList[i][j] === 0) {
                let queue = [[i, j]];
                checkList[i][j] = 1;
                let curNum = 0;

                while (queue.length > 0) {
                    const [x, y] = queue.shift();
                    if (grid[x][y] === 'E') curNum += 1;

                    for (const [dx, dy] of DIRECTIONS) {
                        let nxtX = x + dx, nxtY = y + dy;
                        if (nxtX >= 0 && nxtX < n && nxtY >= 0 && nxtY < m) {
                            if (grid[nxtX][nxtY] !== '#' && checkList[nxtX][nxtY] === 0) {
                                queue.push([nxtX, nxtY]);
                                checkList[nxtX][nxtY] = 1;
                            }
                        }
                    }
                }

                if (curNum < k) ans += 1;
            }
        }
    }

    console.log(ans);
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var directions = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} // 表示四个方向的数组

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    firstLine := strings.Split(scanner.Text(), " ")
    n, _ := strconv.Atoi(firstLine[0])
    m, _ := strconv.Atoi(firstLine[1])
    k, _ := strconv.Atoi(firstLine[2])

    grid := make([]string, n)
    for i := 0; i < n; i++ {
        scanner.Scan()
        grid[i] = scanner.Text()
    }

    ans := 0
    checkList := make([][]int, n)
    for i := range checkList {
        checkList[i] = make([]int, m)
    }

    // 双重循环找到BFS起始点
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] != '#' && checkList[i][j] == 0 {
                queue := [][2]int{{i, j}}
                checkList[i][j] = 1
                curNum := 0

                for len(queue) > 0 {
                    x, y := queue[0][0], queue[0][1]
                    queue = queue[1:]
                    if grid[x][y] == 'E' {
                        curNum++
                    }

                    for _, d := range directions {
                        nxtX, nxtY := x+d[0], y+d[1]
                        if nxtX >= 0 && nxtX < n && nxtY >= 0 && nxtY < m {
                            if grid[nxtX][nxtY] != '#' && checkList[nxtX][nxtY] == 0 {
                                queue = append(queue, [2]int{nxtX, nxtY})
                                checkList[nxtX][nxtY] = 1
                            }
                        }
                    }
                }

                if curNum < k {
                    ans++
                }
            }
        }
    }

    fmt.Println(ans)
}

解法二：DFS

Python

# 题目：2025A-战场索敌
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问


# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]


# 输入行数n，列数m，阈值k
n, m, k = map(int, input().split())
# 输入网格
grid = list()
for _ in range(n):
    grid.append(input())


# 答案变量，用于记录敌人个数大于k的的连通块的个数
ans = 0
# 用于检查的二维矩阵
# 0表示没检查过，1表示检查过了
check_list = [[0] * m for _ in range(n)]

# 构建DFS递归函数
def dfs(check_list, x, y):
    # 声明变量cur_num为全局变量，表示当前DFS过程中，连通块中敌人的个数
    global cur_num
    # 将点(x, y)标记为已检查过
    check_list[x][y] = 1
    # 如果当前位置是敌人，则更新当前连通块的敌人数目cur_num
    if grid[x][y] == "E":
        cur_num += 1
    for dx, dy in DIRECTIONS:
        nxt_x, nxt_y = x + dx, y + dy
        # 若下一个点继续进行dfs，应该满足以下三个条件：
        # 1.没有越界
        # 2.在grid中值为"."或"E"
        # 3.尚未被检查过
        if 0 <= nxt_x < n and 0 <= nxt_y < m:
            if grid[nxt_x][nxt_y] != "#" and check_list[nxt_x][nxt_y] == 0:
                # 可以进行dfs
                dfs(check_list, nxt_x, nxt_y)


# 最外层的大的双重循环，是用来找DFS的起始搜索位置的
for i in range(n):
    for j in range(m):
        # 找到一个"."或"E"，并且这个"."或"E"从未被搜索过：那么可以进行DFS的搜索
        if grid[i][j] != "#" and check_list[i][j] == 0:
            # 初始化当前连通块的敌人数目cur_num为0
            cur_num = 0
            dfs(check_list, i, j)
            # DFS搜索完成，如果cur_num小于k，更新ans
            if cur_num < k:
                ans += 1
                
print(ans)

Java

import java.util.*;

public class Main {
    static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    static int ans = 0;
    static char[][] grid;
    static int[][] checkList;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();

        grid = new char[n][m];
        checkList = new int[n][m];

        for (int i = 0; i < n; i++) {
            String row = scanner.next();
            for (int j = 0; j < m; j++) {
                grid[i][j] = row.charAt(j);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] != '#' && checkList[i][j] == 0) {
                    int[] curNum = new int[]{0};
                    dfs(i, j, curNum);
                    if (curNum[0] < k) {
                        ans++;
                    }
                }
            }
        }

        System.out.println(ans);
    }

    static void dfs(int x, int y, int[] curNum) {
        checkList[x][y] = 1;

        if (grid[x][y] == 'E') {
            curNum[0]++;
        }

        for (int[] direction : DIRECTIONS) {
            int nextX = x + direction[0];
            int nextY = y + direction[1];

            if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length &&
                    grid[nextX][nextY] != '#' && checkList[nextX][nextY] == 0) {
                dfs(nextX, nextY, curNum);
            }
        }
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

// Represent four directions as an array
const vector<pair<int, int>> DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

void dfs(vector<vector<int>>& checkList, vector<string>& grid, int x, int y, int k, int& curNum) {
    // Mark the point (x, y) as checked
    checkList[x][y] = 1;
    // If the current position is an enemy, update curNum
    if (grid[x][y] == 'E') {
        curNum++;
    }
    for (const pair<int, int>& direction : DIRECTIONS) {
        int nextX = x + direction.first;
        int nextY = y + direction.second;
        // If the next point can continue DFS, it should satisfy three conditions:
        // 1. Not out of bounds
        // 2. The value in the grid is "." or "E"
        // 3. Has not been checked yet
        if (0 <= nextX && nextX < grid.size() && 0 <= nextY && nextY < grid[0].size() &&
            (grid[nextX][nextY] != '#' && checkList[nextX][nextY] == 0)) {
            // Continue with DFS
            dfs(checkList, grid, nextX, nextY, k, curNum);
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> grid(n);

    // Input the grid
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    // Answer variable to count the number of connected blocks with more than k enemies
    int ans = 0;

    // Two-dimensional matrix for checking
    // 0 means not checked, 1 means checked
    vector<vector<int>> checkList(n, vector<int>(m, 0));

    // Outermost double loop to find the starting search position for DFS
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Find a "." or "E" and it has not been searched before: then DFS search can be performed
            if (grid[i][j] != '#' && checkList[i][j] == 0) {
                // Initialize the number of enemies in the current connected block curNum to 0
                int curNum = 0;
                dfs(checkList, grid, i, j, k, curNum);
                // If DFS search is complete and curNum is less than k, update ans
                if (curNum < k) {
                    ans++;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>

#define MAX_N 1000
int DIRECTIONS[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向数组
char grid[MAX_N][MAX_N];
int checkList[MAX_N][MAX_N];
int n, m, k;
int curNum, ans = 0;

// DFS递归函数
void dfs(int x, int y) {
    checkList[x][y] = 1;
    if (grid[x][y] == 'E') curNum++;

    for (int i = 0; i < 4; i++) {
        int nxtX = x + DIRECTIONS[i][0];
        int nxtY = y + DIRECTIONS[i][1];
        if (nxtX >= 0 && nxtX < n && nxtY >= 0 && nxtY < m) {
            if (grid[nxtX][nxtY] != '#' && checkList[nxtX][nxtY] == 0) {
                dfs(nxtX, nxtY);
            }
        }
    }
}

int main() {
    scanf("%d %d %d", &n, &m, &k);

    // 输入网格
    for (int i = 0; i < n; i++) {
        scanf("%s", grid[i]);
    }

    // 外层双重循环，寻找DFS起点
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '#' && checkList[i][j] == 0) {
                curNum = 0;
                dfs(i, j);
                if (curNum < k) ans++;
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

Node JavaScript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const DIRECTIONS = [[0, 1], [1, 0], [-1, 0], [0, -1]]; // 表示四个方向的数组
let n, m, k;
let grid = []; // 存储输入的网格
let ans = 0; // 记录满足条件的连通块数量
let curNum = 0; // 当前连通块中敌人数量的计数变量

rl.on('line', (line) => {
    // 第一行输入行数n、列数m和阈值k
    if (!n) {
        [n, m, k] = line.split(' ').map(Number);
    } else {
        // 存储每行的网格数据
        grid.push(line);
        // 当所有行输入完成后，关闭输入
        if (grid.length === n) rl.close();
    }
});

rl.on('close', () => {
    // 初始化检查列表checkList，0表示未检查，1表示已检查
    let checkList = Array.from({ length: n }, () => Array(m).fill(0));

    // 深度优先搜索(DFS)函数
    const dfs = (x, y) => {
        // 将点(x, y)标记为已检查
        checkList[x][y] = 1;
        // 如果当前位置是敌人，则更新当前连通块的敌人数目
        if (grid[x][y] === 'E') curNum++;

        // 遍历四个方向
        for (const [dx, dy] of DIRECTIONS) {
            const nxtX = x + dx, nxtY = y + dy;
            // 检查下一个位置是否满足以下条件：
            // 1. 未越界
            // 2. 不是障碍物
            // 3. 尚未被检查过
            if (nxtX >= 0 && nxtX < n && nxtY >= 0 && nxtY < m) {
                if (grid[nxtX][nxtY] !== '#' && checkList[nxtX][nxtY] === 0) {
                    dfs(nxtX, nxtY); // 递归调用DFS
                }
            }
        }
    };

    // 主循环，查找DFS的起始位置
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            // 找到一个未检查的"."或"E"，可以作为新的连通块起点
            if (grid[i][j] !== '#' && checkList[i][j] === 0) {
                curNum = 0; // 每次新的DFS调用前重置敌人计数
                dfs(i, j); // 调用DFS
                // 如果当前连通块敌人数目小于k，更新答案
                if (curNum < k) ans++;
            }
        }
    }

    // 输出符合条件的连通块数量
    console.log(ans);
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

var (
    directions = [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}} // 表示四个方向的数组
    n, m, k    int
    grid       []string
    checkList  [][]int
    ans        int
    curNum     int
)

func dfs(x, y int) {
    checkList[x][y] = 1
    if grid[x][y] == 'E' {
        curNum++
    }
    for _, d := range directions {
        nxtX, nxtY := x+d[0], y+d[1]
        if nxtX >= 0 && nxtX < n && nxtY >= 0 && nxtY < m {
            if grid[nxtX][nxtY] != '#' && checkList[nxtX][nxtY] == 0 {
                dfs(nxtX, nxtY)
            }
        }
    }
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Scan()
    firstLine := strings.Split(scanner.Text(), " ")
    n, _ = strconv.Atoi(firstLine[0])
    m, _ = strconv.Atoi(firstLine[1])
    k, _ = strconv.Atoi(firstLine[2])

    grid = make([]string, n)
    for i := 0; i < n; i++ {
        scanner.Scan()
        grid[i] = scanner.Text()
    }

    checkList = make([][]int, n)
    for i := range checkList {
        checkList[i] = make([]int, m)
    }

    // 外层双重循环，寻找DFS起点
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] != '#' && checkList[i][j] == 0 {
                curNum = 0
                dfs(i, j)
                if curNum < k {
                    ans++
                }
            }
        }
    }

    fmt.Println(ans)
}

时空复杂度

时间复杂度：O(``NM``)。无论是DFS还是BFS，都需要遍历二维网格中的每一个点。

空间复杂度：O(``NM``)。