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 2

这道题目是一个图论问题，可以使用深度优先搜索或广度优先搜索来解决。具体做法如下：

1. 定义一个二维数组 visited[R][C]，表示每个位置是否被访问过，初始值均为 false。

2. 定义两个计数器，roomCount 和 herdCount，分别表示房间数和牛群数，初始值均为 0。

3. 对于每个未被访问过的位置 (i, j)，进行如下操作：

a. 如果该位置为 '.' 或已被访问过，跳过。

b. 如果该位置为 '#'，进行深度或广度优先搜索，找到与该位置相连的所有 '#'，并打上 visited 标记。

c. 根据相连的 '#' 的数量和位置关系，判断其是房间还是牛群，并增加相应的计数器。

4. 输出房间数和牛群数。

代码实现可以参考以下 Python 代码：