AlgoMooc
← 返回题库

P6200. 最小距离和

中等通过率 32% · 提交 85 · 通过 27
BFS图论矩阵

在一个项目中,小慕负责规划社区垃圾回收的运输路线。 每个居民区的生活垃圾需要由运输车运到最近的垃圾回收站进行处理,目标是计算将所有居民区的垃圾送到回收站所需的最小总路程。 假设居民区和垃圾回收站都位于一个 m 行 * n 列的网格区域上,相邻格子之间的距离为 1,只能上下左右移动;其中 0 表示垃圾回收站,1 表示居民区,2 表示空地,-1 表示障碍物,不可通行。 如果区域内没有居民区或没有垃圾回收站,则最小总路程返回 0。无法到达垃圾回收站的居民区将单独处理,不计入本次总路程中。计算所有居民区垃圾送到垃圾回收站的最小总路程。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行为两个数字 m 和 n,表示区域矩阵的行数和列数,中间使用空格分隔,m和n的范围均为[1,300) 。 接下来的 m 行表示一个 m*n 的区域矩阵数组,每行的元素间以空格分隔,其中元素取值仅为-1(障碍区域)、0(垃圾处理站)、1(小区)、2(空白区域)

输出描述

一个整数,表示所计算的最小距离和。

示例

示例 1

输入

4 4 
1 2 -1 1 
2 0 2 0 
2 2 -1 2 
1 2 1 1

输出

11

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。