题面解释

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

思路:BFS求最短路

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

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

题解分析：

1. BFS的思想：

广度优先搜索（BFS）是解决无权图最短路径问题的经典算法。它的基本思想是：

• 从起点开始，将其加入队列，并标记距离为0。
• 每次从队列中取出一个点，尝试从该点向四个方向扩展（上下左右），并检查扩展的点是否满足条件：
  • 新的点在矩阵范围内；
  • 新的点不是障碍物；
  • 新的点没有被访问过。
• 如果条件都满足，则将该点加入队列，并将其距离更新为当前点的距离加1。
• 当队列为空时，算法结束，最终记录终点的距离。

2. 具体实现步骤：

• 输入数据的处理：首先读入矩阵的大小$m$和$n$，起点和终点的坐标，以及障碍点的数量和位置。我们使用一个二维数组grid来表示矩阵，其中0表示可经过的点，1表示障碍点。
• 距离数组的初始化：使用一个二维数组dist来记录每个点到起点的最短距离。初始时将dist数组全部设置为-1，表示所有点都未访问过。
• BFS过程：
  • 从起点开始，将起点坐标放入队列，并将其距离设为0。
  • 然后每次从队列中取出一个点，检查它的四个相邻点是否可以继续前进（不越界、不是障碍且未访问过），如果可以，则将其加入队列并更新其距离。
• 输出结果：在BFS完成后，输出终点的最短距离。如果终点的距离仍为-1，说明无法到达终点。

3. 边界情况考虑：

• 障碍点完全堵死路径：如果起点和终点被障碍点完全围住，BFS过程中终点的距离不会被更新，最终返回-1。
• 起点与终点重合：如果起点和终点相同，那么直接输出距离0。
• 矩阵边界的处理：BFS扩展时需注意检查新的点是否在矩阵的边界内，防止越界访问。

4. 复杂度分析：

• 时间复杂度：BFS的时间复杂度是$O(m*n)$，其中$m$和$n$是矩阵的长和宽，因为每个点最多被访问一次。
• 空间复杂度：空间复杂度同样为$O(m*n)$，因为我们需要记录每个点的距离以及队列中的点。

代码

x代表行数（纵坐标），y代表列数（横坐标）。左上角是（0，0）

java

import java.util.*;

public class Main {
    static int n, m;
    static int[][] grid;
    static int[][] dist;
    static int[] dx = {0, 0, 1, -1}; // 移动方向，分别为右、左、下、上
    static int[] dy = {1, -1, 0, 0}; // 移动方向，分别为右、左、下、上

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();
        int sy = sc.nextInt();
        int sx = sc.nextInt();
        int ey = sc.nextInt();
        int ex = sc.nextInt();
        grid = new int[n][m];
        dist = new int[n][m];

        // 初始化距离数组为-1，表示尚未访问
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], -1);
        }

        int k = sc.nextInt(); // 不可通过的障碍点数量
        for (int i = 0; i < k; i++) {
            int y = sc.nextInt();
            int x = sc.nextInt();
            grid[x][y] = 1; // 设置障碍点
        }

        // 调用BFS寻找最短路径
        bfs(sx, sy);

        // 输出终点到起点的最短距离
        System.out.println(dist[ex][ey]);
    }

    // BFS算法实现
    static void bfs(int sx, int sy) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sx, sy});
        dist[sx][sy] = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                // 判断新的位置是否在矩阵范围内，且未访问且不是障碍
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1 && grid[nx][ny] == 0) {
                    queue.add(new int[]{nx, ny});
                    dist[nx][ny] = dist[x][y] + 1; // 更新距离
                }
            }
        }
    }
}

python

m = int(input())
n = int(input())
sy, sx = map(int, input().split())
ey, ex = map(int, input().split())
arr = [[0 for _ in range(m)] for _ in range(n)]  # 初始化地图矩阵
k = int(input())  # 障碍点数量
for _ in range(k):
    y, x = map(int, input().split())
    arr[x][y] = 1  # 标记障碍点

dx = [0, 0, 1, -1]  # 方向数组，分别表示右、左、下、上
dy = [1, -1, 0, 0]  # 方向数组，分别表示右、左、下、上
dist = [[-1 for _ in range(m)] for _ in range(n)]  # 初始化距离矩阵为-1

def bfs(x, y):
    q = []
    q.append([x, y])
    dist[x][y] = 0  # 起点距离为0
    while q:
        x, y = q.pop(0)
        for i in range(4):  # 遍历四个方向
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and dist[nx][ny] == -1 and arr[nx][ny] == 0:
                q.append([nx, ny])
                dist[nx][ny] = dist[x][y] + 1  # 更新距离

bfs(sx, sy)
print(dist[ex][ey])  # 输出终点的最短距离

cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n, m;
int grid[1000][1000];
int dist[1000][1000];
int dx[4] = {0, 0, 1, -1}; // 方向数组：右、左、下、上
int dy[4] = {1, -1, 0, 0}; // 方向数组：右、左、下、上

// BFS算法
void bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 检查新的位置是否在矩阵内且未访问且不是障碍
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1 && grid[nx][ny] == 0) {
                q.push({nx, ny});
                dist[nx][ny] = dist[x][y] + 1;  // 更新距离
            }
        }
    }
}

int main() {
    cin >> m >> n;
    int sx, sy, ex, ey;
    cin >> sy >> sx >> ey >> ex;

    memset(grid, 0, sizeof(grid));
    memset(dist, -1, sizeof(dist));  // 初始化距离数组为-1

    int k;  // 障碍数量
    cin >> k;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> y >> x;
        grid[x][y] = 1;  // 设置障碍点
    }

    bfs(sx, sy);

    cout << dist[ex][ey] << endl;  // 输出终点到起点的最短距离
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

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

输入描述

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

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

机房坐标($a1,a2$)

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

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

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

$1<=m,n<=1000$

$0<=k<=100000$

输出描述

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

样例1

输入

11
8
2 3
7 5
6
2 4
3 5
4 4
5 4
6 4
7 4

输出

9

说明

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

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

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

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

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

样例2

输入

3
3 
0 0
2 2
3
0 1
1 1
2 1

输出

-1

说明

$3*3$的矩阵

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

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

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

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