1168: 【6☆】卫星照片 内存限制：128 MB 时间限制：1.000 S 评测方式：文本比较 命题人：admin 提交：256 解决：93 题目描述 农夫john正在研究他的农场的卫星照片。照片为一个R (1 <=R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示，如下图: ．．．．．．．．．．．．．．．．．． ．．＃＃＃＃＃．．．．．．．＃＃．． ．．＃＃＃＃＃．．．．．．＃＃．．． ．．．．．．．．．．．．．．．．．． ＃．．．．．．．＃＃＃．．．．．＃． ＃．．．．．＃＃＃＃＃．．．．．．． 图上的一块相连通的 "#" 表示一群奶牛或一个房间, 两个子"#" 连通的意思是说左右或上下相连.而下面的两块则是分开的: ．．．． ．＃．． ．．＃． ．．．． John现在根据卫星照片上的的这些“#”块的形状来判断哪些是牛群,哪些是房间.如果一个“#”块形状的边是水平或垂直的矩形,则是房间。其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, 1x1)和2群牛。 请根据输入文件中的数据，统计出房间数和牛群数。 数据中牛群不会包围另一个牛群或房间。 输入 第一行，两个整数： R 和 C。 2~R+1行：第 i+1 行表示照片的第 i 行情况，由 C 字符组成。 输出 第一行：房间数。 第二行：牛群数。 样例输入 复制 5 8 #####..# #####.## ......#. .###...# .###..## 样例输出 复制 2 2C++代码

以下是 C++ 实现，与 Python 实现思路类似：

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 75;

int R, C;
char photo[MAXN][MAXN];
bool visited[MAXN][MAXN];
int roomCount, herdCount;

// 深度或广度优先搜索函数
vector<pair<int, int>> dfs(int i, int j) {
    vector<pair<int, int>> herd;  // 记录与该位置相连的所有 '#' 的坐标
    vector<pair<int, int>> stack = {{i, j}};  // 使用栈实现深度优先搜索
    visited[i][j] = true;  // 标记该位置已被访问过
    while (!stack.empty()) {
        auto [x, y] = stack.back();
        stack.pop_back();
        herd.emplace_back(x, y);
        for (auto [dx, dy] : vector<pair<int, int>>{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {  // 遍历上下左右四个方向
            int xx = x + dx, yy = y + dy;
            if (xx >= 0 && xx < R && yy >= 0 && yy < C && photo[xx][yy] == '#' && !visited[xx][yy]) {
                stack.emplace_back(xx, yy);
                visited[xx][yy] = true;
            }
        }
    }
    return herd;
}

int main() {
    cin >> R >> C;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> photo[i][j];
        }
    }

    memset(visited, false, sizeof visited);  // 初始化 visited 数组

    // 遍历每个位置，找到所有房间和牛群并计数
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (photo[i][j] == '#' && !visited[i][j]) {
                auto herd = dfs(i, j);
                if (herd.size() == 1) {  // 如果只有一个 '#'，则是房间
                    ++roomCount;
                } else {  // 判断是否为牛群，即是否是水平或垂直的矩形
                    int minX = R, maxX = -1, minY = C, maxY = -1;  // 初始化最小和最大的行列坐标
                    for (auto [x, y] : herd) {
                        minX = min(minX, x);
                        maxX = max(maxX, x);
                        minY = min(minY, y);
                        maxY = max(maxY, y);
                    }
                    if (maxX - minX + 1 == herd.size() && maxY - minY + 1 == herd[0].second - herd[0].first + 1) {
                        ++herdCount;
                    }
                }
            }
        }
    }

    // 输出房间数和牛群数
    cout << roomCount << endl << herdCount << endl;

    return 0;
}