用C++写一个长方形地图,由n×m个面积相同的正方形小方格组成,小方格有4种颜色,分别用字符'%'、'+'、'#'、和'.'表示,连续一片相同颜色的区域构成一个城镇,求最大城镇的面积
时间: 2024-02-06 20:12:10 浏览: 191
地图四色问题(c++)
4星 · 用户满意度95%
好的,以下是一个基于 DFS 的 C++ 代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1005;
// 地图大小
int n, m;
// 地图数组
char map[MAXN][MAXN];
// 标记数组,标记每个点是否被访问过
bool visited[MAXN][MAXN];
// 方向数组,表示上下左右四个方向
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
// 计算从(x, y)点开始的城镇面积
int dfs(int x, int y, char color) {
// 如果当前点越界或者不是指定颜色,返回0
if (x < 1 || x > n || y < 1 || y > m || map[x][y] != color) {
return 0;
}
// 如果当前点已经被访问过,返回0
if (visited[x][y]) {
return 0;
}
// 标记当前点已经被访问过
visited[x][y] = true;
// 统计当前城镇的面积
int area = 1;
// 搜索上下左右四个方向
for (int i = 0; i < 4; i++) {
area += dfs(x + dx[i], y + dy[i], color);
}
// 返回当前城镇的面积
return area;
}
int main() {
cin >> n >> m;
// 读入地图
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> map[i][j];
}
}
// 初始化标记数组
memset(visited, false, sizeof(visited));
// 遍历每个点,找到最大的城镇面积
int max_area = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!visited[i][j]) {
int area = dfs(i, j, map[i][j]);
max_area = max(max_area, area);
}
}
}
// 输出最大的城镇面积
cout << max_area << endl;
return 0;
}
```
这个代码的思路和之前回答中描述的算法类似,使用 DFS 遍历每个点,统计每个城镇的面积,并记录最大的城镇面积。需要注意的是,这个代码实现中使用了一个 bool 类型的数组 visited,用于标记每个点是否被访问过。
阅读全文