题面解释

某运营商计划在一个用 $m*n$ 矩阵表示的区域内铺设光缆，起点为机房，终点为目标小区。光缆只能沿着矩阵的边铺设（不能走对角线），部分节点由于各种原因无法经过（如输入中的障碍节点）。机房和小区的坐标可以位于矩阵内的任何位置。任务是计算从机房到小区铺设光缆的最短距离，如果无法到达，则返回 $-1$ 。

思路:BFS求最短路

本题大意为：给你一个二维矩阵，里面有若干个点不能通过，求起点到终点的最短距离。

这题是一个非常朴素的BFS求最短路。咱们的题单里大量考察了这个知识点，刷过的同学基本就能通过啦~

P2282.第1题-铺设光缆问题

1000ms

Tried: 2112

Accepted: 587

Difficulty: 3

所属公司 : 华为

算法与标签>BFS

题目内容

某运营商需要在某一区城铺设光缆，起点为机房，终点为某小区，整个区域以一个 $m*n$ 的矩阵表示，光缆沿着矩阵的边铺设(不允许走对角线)，区域内有些节点可以经过，但有些节点(如图红色 $x$ 的位置,输入时给定) 因为各种因素无法经过，起点的机房与终点的小区可能在区域内的任何位置，计算从机房到目标小区铺设光缆的最短距离(如果光缆无法从起点机房铺设到达目标小区，返回 $-1$ )。

hw-1

输入描述

$m$ 矩阵宽(横轴点数量，例如图示为 $11$ ，以 $0$ ~ $10$ 作为下标)

$n$ 矩阵高(纵轴点数量，例如图示为 $8$ ，以 $0$ ~ $7$ 作为下标)

机房坐标( $a1,a2$ )

目标小区坐标( $b1,b2$ )

矩阵内不允许经过的节点数量 $k$

依次为这些不允许经过的节点坐标

$1<=m,n<=1000$

$0<=k<=100000$

输出描述

从机房到目标小区铺设光缆的最短距离

样例1

输入

输出

说明

$11*8$ 的矩阵(横轴坐标 $0$ ~ $10$ ，纵轴坐标 $0$ ~ $7$ )

起始点(机房)为坐标( $2\ 3$ )

目标点(要连到的小区)为坐标( $7\ 5$ )

矩阵内不允许经过的节点数为 $6$ 个

依次给出这些不允许经过的节点坐标

样例2

输入

输出

-1

说明

$3*3$ 的矩阵

起始点(机房)为坐标( $0\ 0$ )

目标点(要连到的小区)为坐标( $2\ 2$ )

矩阵内不允许经过的节点数为 $3$ 个

依次给出这些不允许经过的节点坐标

输入

预期输出（选填）

题面解释

思路:BFS求最短路

P2282.第1题-铺设光缆问题

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About