题目描述
一个仓库的平面图是 行 列的字符网格:# 表示货架,. 表示通道。
上下左右相邻的货架属于同一个货区(斜着相邻不算)。请你统计:
- 一共有多少个货区;
- 最大的货区里有多少个货架。
输入格式
第一行两个整数 。
接下来 行,每行一个长度为 的字符串,只含 # 和 .。
输出格式
一行两个整数:货区个数、最大货区面积(货架个数)。若没有任何货架,输出 0 0。
样例 1
输入
3 4
#..#
.##.
#..#
输出
3 2
说明:三个货区分别是左上角 #、中间的两个 #((2,2) 与 (2,3) 左右相邻)、右下角 #;最大面积 2。
样例 2
输入
1 6
##.##.
输出
2 2
数据范围与子任务
| 测试点 | 规模与性质 | 分值 |
|---|---|---|
| ,货区有多个 | ||
| 只有一行或一列( 或 ),长度 ,货架分成 1~3 大段 | ||
| ,但所有货架连成一片(只有一个货区) | ||
| ,无特殊性质 |
提示
递归写法的边界:把 DFS 写成递归函数,在小网格上没问题;但当一整片货区有几十万个货架时,
递归深度会超过默认栈空间(约 8 MB),程序会直接崩溃(表现为 RE / 段错误),一分都拿不到。
要么把 DFS 改成显式栈/队列的迭代写法,要么把递归深度控制在安全范围内。