/ phigros / 题库 /

space

space

测试数据来自 wjszez/1519

【问题描述】
农民约翰的牛终于乘着他们的奶牛飞船发射升空,现在它们正在太空中飞行。它们想到它们位于木星的卫星Io上亲戚那去,但是他们必须第一次飞越危险的小行星群。

Bessie正驾驶飞船通过N x N (1≤N≤1,000)的危险区域。小行星群由许多1 x 1的方块组成(同一区域的方块与邻近的方块有相同的边)。
下面是一个10 x 10的区域。每个'*'表示一个小行星,每个'.'表示空的区域。
...**..... ...11.....
.*........ .2........
......*... ......3...
...*..*... ...3..3...
..*****... ..33333...
...*...... ...3......
....***... ....444...
.*..***... .5..444...
.....*...* ......4...6
..*....... ..7........

我们容易发现有7个小行星群在这个区域。现在Bessie决定只保留K(0≤k≤小行星群数)个小行星群,请帮助Bessie计算最少要清除几个小行星。
【输入格式】
* 一行: 两个正整数N和K,用一个空格隔开
* 第2..N+1行: 第i+1行包含一个长度为N的字符串表示通过的区域情况
【输出格式】
* 一行: 一个整数表示Bessie计算至少要清除几个小行星
【样例输入】(space.in):
10 5
...**.....
.*........
......*...
...*..*...
..*****...
...*......
....***...
.*..***...
.....*...*
..*.......

【样例输出】(space.out):
2

信息

ID
1023
难度
9
分类
(无)
标签
递交数
1
已通过
1
通过率
100%
上传者