3 solutions

  • 0
    @ 2024-10-25 21:51:56 
    from collections import deque
n = int(input())
m = int(input())
s_x,s_y = map(int,input().split())
e_x,e_y = map(int,input().split())
g = [[0 for _ in range(m)] for _ in range(n)]
k = int(input())
for i in range(k):
    x,y = map(int,input().split())
    g[x][y] = 1
dis = [[-1 for _ in range(m)] for _ in range(n)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(x,y):
    q = deque([(x,y)])
    dis[x][y]=0
    while q:
        x,y = q.popleft()
        for i in range(4):
            new_x = x+dx[i]
            new_y = y+dy[i]
            if 0<=new_x<n and 0<=new_y<m and dis[new_x][new_y]==-1 and g[new_x][new_y]==0:
                dis[new_x][new_y] = dis[x][y]+1
                q.append((new_x,new_y))

bfs(s_x,s_y)
print(dis[e_x][e_y])
    • 0
      @ 2024-10-12 16:36:41

      #include #include #include #include using namespace std;

      struct Point { int x, y; Point(int x, int y) : x(x), y(y) {} };

      int bfs(const vector<vector>& grid, Point start, Point end) { if (!grid[start.x][start.y] || !grid[end.x][end.y]) return -1; // 起点或终点不可通行

      int m = grid.size();
int n = grid[0].size();
vector<vector<int>> distances(m, vector<int>(n, -1));
queue<Point> q;

// 方向数组，用于表示上、下、左、右四个方向
int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};

// 初始化
q.push(start);
distances[start.x][start.y] = 0;

while (!q.empty()) {
    Point current = q.front();
    q.pop();
    
    for (int i = 0; i < 4; i++) {
        int nx = current.x + directions[i][0];
        int ny = current.y + directions[i][1];
        
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] && distances[nx][ny] == -1) {
            distances[nx][ny] = distances[current.x][current.y] + 1;
            if (nx == end.x && ny == end.y) {
                return distances[nx][ny]; // 找到终点
            }
            q.push(Point(nx, ny));
        }
    }
}
return -1; // 未能到达终点

      }

      int main() { int m, n, a1, a2, b1, b2, k; cin >> m >> n; cin >> a1 >> a2; cin >> b1 >> b2; cin >> k;

      vector<vector<bool>> grid(m, vector<bool>(n, true));

for (int i = 0; i < k; i++) {
    int x, y;
    cin >> x >> y;
    grid[x][y] = false; // 标记不可通过的节点
}

int distance = bfs(grid, Point(a1, a2), Point(b1, b2));
cout << distance << endl;

return 0;

      }

      • 0
        @ 2024-10-9 20:42:36

        题面解释

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

        思路:BFS求最短路

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

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

        题解分析：

        1. BFS的思想：

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

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

        2. 具体实现步骤：

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

        3. 边界情况考虑：

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

        4. 复杂度分析：

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

        代码

        java

        import java.util.*;

public class ShortestPathBFS {
    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);

        n = sc.nextInt();
        m = sc.nextInt();
        int sx = sc.nextInt();
        int sy = sc.nextInt();
        int ex = sc.nextInt();
        int ey = 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 x = sc.nextInt();
            int y = 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

        n = int(input())
m = int(input())
sx, sy = map(int, input().split())
ex, ey = map(int, input().split())
arr = [[0 for _ in range(m)] for _ in range(n)]  # 初始化地图矩阵
k = int(input())  # 障碍点数量
for _ in range(k):
    x, y = 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 >> n >> m;
    int sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;

    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 >> x >> y;
        grid[x][y] = 1;  // 设置障碍点
    }

    bfs(sx, sy);

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

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

        • 1

        2024.10.9-秋招-第1题-铺设光缆问题

        Information

        ID
        136
        Time
        1000ms
        Memory
        256MiB
        Difficulty
        3
        Tags
        # Submissions
        768
        Accepted
        185
        Uploaded By
        1. About
        2. Contact Us
        3. Privacy
        4. Terms of Service
        5. Copyright Complaint
        6. Language
        7. Legacy mode
        8. Theme
        2. 湘ICP备2023007293号
        3. Worker 0, 33ms
        4. Powered by Hydro v4.14.1 Community