给定一个 n*n 的地图。地图是上下左右四联通的,但是不能斜向行走。
其中:
*代表障碍,不可通行;
.代表路,可以通行;
#代表房子。房子也是可以通行的。
现在需要在一些地方安排一些超市(不能安排在障碍物上,可以安排在路上或者房子上,超市也是可以通行的),每个房子至少可以到达一个超市。同时由于成本原因,超市的数量需要尽可能的少。
在超市数量最少的情况下,每个房子到达最近的超市的距离之和需要尽可能小。
你的任务是计算超市最少的数量,以及最小的距离之和。
3 #.# .** *.#
2 2
下标从 0 开始,第一个超市安排的位置是(0,1),第二个超市安排的位置是(2,2)。 三个房子到超市的距离分别为1、1、0。这样可以使得三个房子都能到达超市,并且所需超市数量最少,总距离之和也最少。
注意:超市直接建在房子上距离为 0。如果没有房子,则不需要建超市。
选择合适的字体大小
选择合适的主题