首页 > 试题广场 >

安排超市

[编程题]安排超市
  • 热度指数:857 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个n*n的地图。地图是上下左右四联通的,不能斜向行走:
*代表障碍,不可通行。
.代表路,可以通行。
#代表房子。房子也是可以通行的。

小红现在需要在一些地方安排一些超市(不能安排在障碍物上,可以安排在路上或者房子上。超市也是可以通行的)。
小红希望每个房子至少可以到达一个超市。同时由于成本原因,小红希望超市的数量尽可能少。
在超市数量最少的情况下,小红希望每个房子到达最近的超市的距离之和尽可能小。
她想知道超市最少的数量,以及最小的距离之和。你能帮帮她吗?

输入描述:
第一行一个正整数n,代表地图的大小。( 1<=n<=50 )
接下来的n行,每行一个长度为n的字符串,表示整个地图。保证输入合法。


输出描述:
输出两个整数,用空格隔开。分别代表超市的最小数量、最小的距离之和。
示例1

输入

3
#.#
.**
*.#

输出

2 2

说明

下标从1开始,第一个超市安排的位置是(1,2),第二个超市安排的位置是(3,3)。三个房子到超市的距离分别为1,1,0。 
示例2

输入

3
#*#
.**
*.#

输出

3 0

说明

分别在三个房子上建3个超市即可。 
示例3

输入

2
.*
*.

输出

0 0

说明

没有房子,所以不用造超市 

这道题你会答吗?花几分钟告诉大家答案吧!

问题信息

上传者:小小
难度:
0条回答 2710浏览

热门推荐

通过挑战的用户

安排超市