题目描述

在一个大小为 ( N \times M ) 的战场地图上，地图中的点可以是墙壁 #、空地 . 或敌人 E。墙壁将地图分隔成多个区域，而相邻的空地和敌人组成一个区域。我们的任务是统计那些敌人数量小于 ( K ) 的区域的总数。

输入描述

• 第一行输入三个整数 ( N, M, K )，分别表示地图的行数、列数和敌人数量的阈值。
• 接下来的 ( N ) 行，每行包含 ( M ) 个字符，表示地图的具体内容。

输出描述

• 输出一个整数，表示敌人数小于 ( K ) 的区域数量。

解题思路

这道题的核心在于标记搜索法（DFS/BFS），我们可以按以下步骤解决：

1. 初始化：读取输入数据并初始化一个标记数组 visited 来记录已经访问过的点。

2. 遍历地图：对于每个点，如果该点是空地 . 且没有被访问过，则启动一次深度优先搜索（DFS）来探索该区域。

3. 深度优先搜索：

   • 在 DFS 中，从当前点开始，记录该区域内敌人 E 的数量。
   • 通过四个方向递归地访问所有相连的空地和敌人。
   • 在遍历过程中，标记已经访问的点，以防重复计数。

4. 统计满足条件的区域：完成 DFS 后，根据统计到的敌人数量判断该区域是否符合条件（敌人数量小于K，如果符合，则增加计数器。

5. 输出结果：最后输出满足条件的区域数量。

时间复杂度

算法的时间复杂度为 ( O(NM) )，每个点至多被访问一次，因此该算法在给定的约束范围内（ ( N, M) <=100 ）是高效的。

代码

Python

import sys
sys.setrecursionlimit(11000)  # 将递归深度限制设置为1500
def count_areas_with_few_enemies(n, m, k, mp):
    # 定义方向数组
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    vis = [[False] * m for _ in range(n)]
    def dfs(x, y):
        nonlocal em
        if mp[x][y] == 'E':
            em += 1
        #修改函数外的vis数组
        
        vis[x][y] = True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 确保 nx 和 ny 在合法范围内
            if 0 <= nx < n and 0 <= ny < m and not vis[nx][ny] and (mp[nx][ny] == '.' or mp[nx][ny] == 'E'):
                dfs(nx, ny)

    ans = 0  # 满足条件的区域数量

    for i in range(n):
        for j in range(m):
            if not vis[i][j] and (mp[i][j] == '.' or mp[i][j] == 'E'):
                em = 0  # 重置当前区域的敌人数量
                dfs(i, j)  # 从当前点开始DFS
                if em < k:
                    ans += 1  # 判断敌人数量是否小于等于K

    return ans

# 输入部分
n, m, k = map(int, input().strip().split())
mp = [input().strip() for _ in range(n)]

# 输出结果
result = count_areas_with_few_enemies(n, m, k, mp)
print(result)

Cpp

#include <bits/stdc++.h>
using namespace std;

int n, m, k;                  // 地图的行数、列数和敌人数量的阈值
char mp[105][105];           // 地图数组
bool vis[105][105];          // 访问标记数组
int enemyCount = 0;          // 当前区域内敌人的数量
int dx[] = {0, 0, 1, -1};    // 方向数组，用于上下左右移动
int dy[] = {1, -1, 0, 0};    // 方向数组，用于上下左右移动

// 深度优先搜索函数
void dfs(int x, int y) {
    if (mp[x][y] == 'E') enemyCount++;  // 如果当前点是敌人，数量加一
    vis[x][y] = true;                    // 标记当前点为已访问

    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        // 判断新位置是否在边界内且未被访问且是空地或敌人
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && 
            !vis[nx][ny] && (mp[nx][ny] == '.' || mp[nx][ny] == 'E')) {
            dfs(nx, ny);  // 递归调用DFS
        }
    }
}

int main() {
    cin >> n >> m >> k;  // 输入行数、列数和敌人数量阈值

    // 输入地图
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    int ans = 0;  // 满足条件的区域数量
    // 遍历地图
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            // 如果当前点未访问且是空地或敌人
            if (!vis[i][j] && (mp[i][j] == '.' || mp[i][j] == 'E')) {
                enemyCount = 0;  // 重置当前区域的敌人数量
                dfs(i, j);       // 从当前点开始DFS
                if (enemyCount < k) ans++;  // 判断敌人数量是否小于等于K
            }
    
    cout << ans << endl;  // 输出结果
    return 0;
}

JAVA

import java.util.Scanner;

public class Main {
    static int n, m, k;
    static char[][] mp = new char[105][105];
    static boolean[][] vis = new boolean[105][105];
    static int enemyCount = 0;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    static void dfs(int x, int y) {
        if (mp[x][y] == 'E') enemyCount++;
        vis[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && 
                !vis[nx][ny] && (mp[nx][ny] == '.' || mp[nx][ny] == 'E')) {
                dfs(nx, ny);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        sc.nextLine(); // 处理换行符

        for (int i = 1; i <= n; i++) {
            String line = sc.nextLine();
            for (int j = 1; j <= m; j++) {
                mp[i][j] = line.charAt(j - 1);
            }
        }

        int ans = 0; // 满足条件的区域数量
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!vis[i][j] && (mp[i][j] == '.' || mp[i][j] == 'E')) {
                    enemyCount = 0; // 重置当前区域的敌人数量
                    dfs(i, j); // 从当前点开始DFS
                    if (enemyCount < k) ans++; // 判断敌人数量是否小于等于K
                }
            }
        }

        System.out.println(ans); // 输出结果
        sc.close();
    }
}

题目内容

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

输入描述

第一行输入为 $N,M,K$

• $N$ 表示地图的行数，$M$ 表示地图的列数， $K$ 表示目标敌人数量
• $N，M<=100$

之后为一个 $N×M$ 大小的字符数组。

输出描述

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

样例1

输入

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

输出

1

说明

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