J. 【入门】卫星照片 USACO 2005 NOV

    传统题 1000ms 128MiB

【入门】卫星照片 USACO 2005 NOV

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

农场主约翰给他的农场买了WHW * H像素的卫星照片($1 \leqslant W \leqslant 80, 1 \leqslant H \leqslant 1000$),希望找出最大的"连续的"(互相连接的)牧场。对于一个牧场的任何一对像素,其中一个像素如果能横向的或纵向的与属于这个牧场的另一个像素相连,这样的牧场称作是连续的。 (很容易创建形状稀奇古怪的牧场,甚至是围着其它圆圈的圆圈。)

每一张照片都数字化的抽象了,牧场区显示为"*",非牧场区显示为"."。下面是一个10 * 5的卫星照片样例:

..*.....**
.**..*****
.*...*....
..****.***
..****.***

这张照片显示了大小分别为4、16、6个像素的连续牧场区。帮助农场主约翰在他的每张卫星照片中找到最大的连续牧场。

输入格式

第1行: 两个由空格分开的整数,WWH H

第2到HH+1行: 每一行包含WW个"*"或者".",代表卫星照片的横向行。

输出格式

最大连续牧场的大小。

样例

10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***
16

C2026届树、图论、最短路

未认领
状态
已结束
题目
14
开始时间
2025-10-25 0:00
截止时间
2025-11-2 23:59
可延期
24 小时