给定一个n*n的地图。地图是上下左右四联通的,不能斜向行走:
*代表障碍,不可通行。
.代表路,可以通行。
#代表房子。房子也是可以通行的。
小红现在需要在一些地方安排一些超市(不能安排在障碍物上,可以安排在路上或者房子上。超市也是可以通行的)。
小红希望每个房子至少可以到达一个超市。同时由于成本原因,小红希望超市的数量尽可能少。
在超市数量最少的情况下,小红希望每个房子到达最近的超市的距离之和尽可能小。
她想知道超市最少的数量,以及最小的距离之和。你能帮帮她吗?
第一行一个正整数n,代表地图的大小。( 1<=n<=50 ) 接下来的n行,每行一个长度为n的字符串,表示整个地图。保证输入合法。
输出两个整数,用空格隔开。分别代表超市的最小数量、最小的距离之和。
3 #.# .** *.#
2 2
下标从1开始,第一个超市安排的位置是(1,2),第二个超市安排的位置是(3,3)。三个房子到超市的距离分别为1,1,0。
3 #*# .** *.#
3 0
分别在三个房子上建3个超市即可。
2 .* *.
0 0
没有房子,所以不用造超市
这道题你会答吗?花几分钟告诉大家答案吧!