A70663. 卫星照片
编程题
提高
知识点
题目描述
农夫约翰总是想要一个农场的地图，所以他拍摄了一张 N 行 M 列的卫星照片。一部分的照片看起来像这样：
..................
..#####.......##..
..#####......##...
..................
#.......###.....#.
#.....#####.......
他认为每个联通块都是一个谷仓或一头奶牛。联通块由若干个彼此水平或垂直相邻的 '＃' 符号组成。以下的照片被认为是两个联通块：
....
.#..
..#.
....
农夫约翰认为一个联通块是谷仓，当且仅当它是一个完整的矩形，否则该联通块是一头奶牛。在第一张照片上面，有三个谷仓（大小分别为 2 \times 1 , 2 \times 5 和 1 \times 1 ）和两头奶牛。 计算他的卫星照片中谷仓和奶牛的数量。
输入格式
行 1：两个空格分隔的整数： N 和 M ( N,M \le 80)。
行 2..N + 1：行 i + 1 表示照片的行 i 包含 M 个字符（且不含空格）。
输出格式
行1：照片中的谷仓数量。
行2：照片中的奶牛数量。
输入输出样例
输入 #1
5 8 #####..# #####.## ......#. .###...# .###..##
输出 #1
2 2
说明/提示
## 思路
「卫星照片」用深度优先搜索：沿一条路走到底再回溯，注意标记访问。
## 步骤
1. 读入图或网格。
2. 从起点 DFS，标记 vis，扩展相邻状态。
3. 在边界处更新答案或输出路径，回溯时恢复。
「卫星照片」用深度优先搜索：沿一条路走到底再回溯，注意标记访问。
## 步骤
1. 读入图或网格。
2. 从起点 DFS，标记 vis，扩展相邻状态。
3. 在边界处更新答案或输出路径，回溯时恢复。