最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 问题 AK: L12-4 广度优先遍历应用 - 练习5

    正文概述 网友投稿   2026-01-22 15:59:52  

    题目描述

    浩瀚的星空可视为一个长为N、宽为M的矩阵,矩阵中共有N×M个位置,一个位置可以用坐标(i,j)(1≤i≤N,1≤j≤M)来表示。每个位置上可能是空的,也可能有一个星星。 对于一个位置(i,j),与其相邻的位置有左边、左上、上面、右上、右边、右下、下面、左下8个位置。相邻位置上的星星被视为同一个星座,这种关系有传递性,例如若(1,1),(1,2),(1,3)三个位置上都有星星,那么这三个星星视为同一个星座。包含的星星数量相同的星座被视为一个星系(一个星系中的星座不一定相邻),星系的大小为星系中包含的所有星星数量。 由于小美太喜欢面前的星空了,她想让小帅帮他求出星空中有多少个星系,以及最大的星系有多大。

    输入

    第一行两个整数N,M(1<=N,M<=1000)表示矩阵的长宽。 接下来N行每行M个字符,每个字符只可能是.或*。这N行中第i行的第j个字符是*表示位置(i,j)上有一个星星,否则表示它是空的。

    输出

    仅一行两个整数,用空格分隔开,分别表示星系的数量与最大星系的大小。

    样例输入

    5 7
    *......
    ..**..*
    .*...*.
    ...*...
    ....*..

    样例输出

    3 4
    信息学奥赛网,一个优质的源码资源平台!
    信息学奥赛网 » 问题 AK: L12-4 广度优先遍历应用 - 练习5