‹ 上一题 下一题 ›

02632. 仓库分区 未做

1000 ms 256 MB 测试点 20 通过率 100% 自拟题部分分专项搜索深度优先搜索广度优先搜索

题目描述

一个仓库的平面图是 行 列的字符网格:# 表示货架,. 表示通道。

上下左右相邻的货架属于同一个货区(斜着相邻不算)。请你统计:

  1. 一共有多少个货区;
  2. 最大的货区里有多少个货架。

输入格式

第一行两个整数 。

接下来 行,每行一个长度为 的字符串,只含 # 和 .。

输出格式

一行两个整数:货区个数、最大货区面积(货架个数)。若没有任何货架,输出 0 0。

样例 1

输入

3 4
#..#
.##.
#..#

输出

3 2

说明:三个货区分别是左上角 #、中间的两个 #((2,2) 与 (2,3) 左右相邻)、右下角 #;最大面积 2。

样例 2

输入

1 6
##.##.

输出

2 2

数据范围与子任务

测试点 规模与性质 分值
,货区有多个
只有一行或一列( 或 ),长度 ,货架分成 1~3 大段
,但所有货架连成一片(只有一个货区)
,无特殊性质

提示

递归写法的边界:把 DFS 写成递归函数,在小网格上没问题;但当一整片货区有几十万个货架时,
递归深度会超过默认栈空间(约 8 MB),程序会直接崩溃(表现为 RE / 段错误),一分都拿不到。
要么把 DFS 改成显式栈/队列的迭代写法,要么把递归深度控制在安全范围内。

输入
输出

            
答案