#P3217. 战场索敌(200分)
-
1000ms
Tried: 153
Accepted: 39
Difficulty: 3
所属公司 :
华为od
战场索敌(200分)
题目描述
在一个大小为 ( N \times M ) 的战场地图上,地图中的点可以是墙壁 #、空地 . 或敌人 E。墙壁将地图分隔成多个区域,而相邻的空地和敌人组成一个区域。我们的任务是统计那些敌人数量小于 ( K ) 的区域的总数。
输入描述
- 第一行输入三个整数 ( N, M, K ),分别表示地图的行数、列数和敌人数量的阈值。
- 接下来的 ( N ) 行,每行包含 ( M ) 个字符,表示地图的具体内容。
输出描述
- 输出一个整数,表示敌人数小于 ( K ) 的区域数量。
解题思路
这道题的核心在于标记搜索法(DFS/BFS),我们可以按以下步骤解决:
-
初始化:读取输入数据并初始化一个标记数组
visited来记录已经访问过的点。 -
遍历地图:对于每个点,如果该点是空地
.且没有被访问过,则启动一次深度优先搜索(DFS)来探索该区域。 -
深度优先搜索:
- 在 DFS 中,从当前点开始,记录该区域内敌人
E的数量。 - 通过四个方向递归地访问所有相连的空地和敌人。
- 在遍历过程中,标记已经访问的点,以防重复计数。
- 在 DFS 中,从当前点开始,记录该区域内敌人
-
统计满足条件的区域:完成 DFS 后,根据统计到的敌人数量判断该区域是否符合条件(敌人数量小于K,如果符合,则增加计数器。
-
输出结果:最后输出满足条件的区域数量。
时间复杂度
算法的时间复杂度为 ( 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