2345. 最大种植面积
1000ms
256MB
简单
广度优先搜索
BFS
题目描述
给定一个大小为 $n \times m$ 的网格地图。其中，字符 `#` 代表土地，`.` 代表溪水。
我们把在**上下左右**四个方向上相邻的 `#` 连通区域称为一块“种植面积”。
请编写程序，计算并输出**最大的一块种植面积**是多少。如果网格中不存在任何土地（连通块），请输出 -1。
**要求：必须使用广度优先搜索（BFS）算法实现。**
输入格式
- 第一行包含两个正整数 $n$ 和 $m$ ($1 < n, m < 20$)，分别表示地图的行数和列数。
- 接下来 $n$ 行，每行包含一个长度为 $m$ 的由 `.` 和 `#` 组成的字符串，代表地图的每一行。字符之间无空格。
输出格式
- 输出一个整数，表示最大的连通块面积。若没有找到任何连通块，输出 -1。
样例 1
输入 (Input)
9 3 .## .#. #.. ##. #.# ... ..# ### #.#
输出 (Output)
6
样例说明
在输入中，最大的连通块位于最下方：
(7,3)、(8,1)、(8,2)、(8,3)、(9,1)、(9,3) 这 6 个点通过上下左右方向互相连通，构成了一个面积为 6 的连通块。这是所有连通块中面积最大的一个，因此输出 6。
- $1 < n, m < 20$。
- **算法提示**：
由于要求使用**广度优先搜索（BFS）**：
1. 遍历 $n \times m$ 网格。如果遇到一个 `#` 且该点未被访问过，则以该点为起点启动一次 BFS。
2. 在 BFS 过程中，使用队列（queue）进行层序遍历，每次拓展上下左右四个方向的邻居。如果邻居是 `#` 且未被访问，则将其入队、标记为已访问，并将当前连通块的累加面积加 1。
3. BFS 结束后，更新全局最大面积 `max_area`。
4. 遍历完全图后，若 `max_area` 仍为初始值 0，则说明没有土地，输出 -1。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功