在一个由 m
行 n
列的区域矩阵中,环卫工人需要将小区的生活垃圾送到最近的垃圾回收站。矩阵中的元素取值为:
0
:垃圾处理站1
:小区2
:空白区域-1
:障碍区域相邻点的距离为 1,且只能上下左右移动。要求计算所有小区垃圾送到垃圾回收站的最小距离和。如果矩阵中没有小区或垃圾回收站,则返回 0
。无法到达垃圾回收站的小区将不计入距离和中。
本题为2024年9月11日华为机考原题
华为机考的介绍点击这里
每天早晨,环卫工人需要处理各个小区的生活垃圾,每个小区的生活垃圾由一队坏卫工人负责运送到最近的垃圾回收站进行处理,求将所有小区垃圾送到垃圾回收站的最小距离和。
假设小区和垃圾回收站都在都在一个m行x n列的区域矩阵上,相邻点的距离为1,只能上下左右移动;其中0表示垃圾处理站,1表示小区,2表示空白区域,−1表示障碍区域不可通行。
区域内如果没有小区或者没有垃圾回收站,则最小距离和返回0。
无法到达垃圾回收站的小区会单独处理,不计入本次距离和中。
计算所有小区垃圾送到垃圾回收站的最小距离和。
第一行为两个数字m和n的和,表示区域矩阵的行数和列数,中间使用空格分隔,m和n的范围均为[1,300]。
接下来的m行表示一个m×n的区域矩阵数组,每行的元素间以空格分隔,其中元素取值仅为−1(障碍区域)、
0(垃圾处理站)、1(小区)、2(空白区域)。
一个整数,表示所计算的最小距离和。
输入
4 4
1 2 -1 1
2 0 2 0
2 2 -1 2
1 2 1 1
输出
11
说明
如图所示,位置[0,0]、[0,3]、[3,0]、[3,2]、[3,3]是小区,位置[1,1]、[1,3]是垃圾站,位置[0,2]、[2,2]是
障碍,无法通行,5个小区,2个垃圾站,小区到垃圾站的最小路径是2+3+1+3+2=11。
对于位置[3,2]的小区,可以将垃圾运送到垃圾站[1,1]、[1,3],两者的距离是一样的。
题解图示仅以到[1,3]垃圾站进行说明。
输入
2 3
0 -1 1
1 -1 2
输出
1
说明
如图所示,位置[0,2]、[1,0]小区,位置[0,0]是垃圾站,位置[0,1]、[1,1]是障碍,无法通行,2个小区,1个垃圾站,小区到垃圾站的最小路径是1+0=1。