1. Job Roadmap
  2. Home
  3. Problem Set
  4. codenotelist
  5. Forum
  6. course
  7. Shore Share Sessions
  8. Record
  1. Login
  2. Sign Up
  3. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
    ZhContent TextSol video solution AI分析

题目大意:

在一个由 m 行 n 列的区域矩阵中,环卫工人需要将小区的生活垃圾送到最近的垃圾回收站。矩阵中的元素取值为:

  • 0:垃圾处理站
  • 1:小区
  • 2:空白区域
  • -1:障碍区域

相邻点的距离为 1,且只能上下左右移动。要求计算所有小区垃圾送到垃圾回收站的最小距离和。如果矩阵中没有小区或垃圾回收站,则返回 0。无法到达垃圾回收站的小区将不计入距离和中。

P14362.【广度优先搜索4】最小距离和

    1000ms Tried: 82 Accepted: 23 Difficulty: 5
    算法与标签>BFS

本题为2024年9月11日华为机考原题

华为机考的介绍点击这里

题目内容

每天早晨,环卫工人需要处理各个小区的生活垃圾,每个小区的生活垃圾由一队坏卫工人负责运送到最近的垃圾回收站进行处理,求将所有小区垃圾送到垃圾回收站的最小距离和。

假设小区和垃圾回收站都在都在一个mmm行xxx nnn列的区域矩阵上,相邻点的距离为111,只能上下左右移动;其中000表示垃圾处理站,111表示小区,222表示空白区域,−1-1−1表示障碍区域不可通行。

区域内如果没有小区或者没有垃圾回收站,则最小距离和返回000。

无法到达垃圾回收站的小区会单独处理,不计入本次距离和中。

计算所有小区垃圾送到垃圾回收站的最小距离和。

输入描述

第一行为两个数字mmm和nnn的和,表示区域矩阵的行数和列数,中间使用空格分隔,mmm和nnn的范围均为[1,300][1,300][1,300]。

接下来的mmm行表示一个m×nm×nm×n的区域矩阵数组,每行的元素间以空格分隔,其中元素取值仅为−1-1−1(障碍区域)、

000(垃圾处理站)、111(小区)、222(空白区域)。

输出描述

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

样例1

输入

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

输出

11

说明

图1

如图所示,位置[0,0]、[0,3]、[3,0]、[3,2]、[3,3][0,0]、[0,3]、[3,0]、[3,2]、[3,3][0,0]、[0,3]、[3,0]、[3,2]、[3,3]是小区,位置[1,1]、[1,3][1,1]、[1,3][1,1]、[1,3]是垃圾站,位置[0,2]、[2,2][0,2]、[2,2][0,2]、[2,2]是

障碍,无法通行,555个小区,222个垃圾站,小区到垃圾站的最小路径是2+3+1+3+2=112+3+1+3+2=112+3+1+3+2=11。

对于位置[3,2][3,2][3,2]的小区,可以将垃圾运送到垃圾站[1,1][1,1][1,1]、[1,3][1,3][1,3],两者的距离是一样的。

题解图示仅以到[1,3][1,3][1,3]垃圾站进行说明。

样例2

输入

2 3
0 -1 1
1 -1 2

输出

1

说明

图2

如图所示,位置[0,2]、[1,0][0,2]、[1,0][0,2]、[1,0]小区,位置[0,0][0,0][0,0]是垃圾站,位置[0,1]、[1,1][0,1]、[1,1][0,1]、[1,1]是障碍,无法通行,222个小区,111个垃圾站,小区到垃圾站的最小路径是1+0=11+0=11+0=1。

开通会员即可查看完整视频题解: 1.题目讲解 2.思路分析 3.逐行代码手写

登录后即可使用 AI 分析。

模式
倒计时时长
:

最长 10 小时 59 分;应用后按此时长重新开始。

提示:点击提交记录在左侧题面区域查看详情
题库
AI分析设置
留空使用官方API Key,每天有次数限制(自定义API Key仅限会员和管理员使用,不限次数)
会员和管理员可切换模型;切到 Kimi/智谱/通义/豆包时需填写对应供应商 API Key
升级会员,可将运行与提交冷却时间缩短至 1 秒起

Status

  • Judging Queue
  • Service Status

Development

  • Open Source

Support

  • Help
  • Contact Us

About

  • About
  • Privacy
  • Terms of Service
  • Copyright Complaint
  1. Language
    1. English
    2. 한국어
    3. 简体中文
    4. 正體中文
  2. Legacy mode
  3. Theme
    1. Light
    2. Dark
  1. 京ICP备2025123107号-1
  2. Worker 1, 49ms
  3. Powered by Hydro v5.0.0-beta.18 Community
CLOSE


ScanQRCodePrompt

请使用微信扫描下方二维码完成注册

Forgot password or username?