解题思路

BFS求最短路径解题思路

1. 问题分析

  • 二维网格中找最短路径
  • 可以上下左右四个方向移动
  • 有障碍物不能通过
  • 需要判断是否能到达目标点

2. 解题步骤

  1. 数据结构

    - 使用二维数组存储网格
- 使用队列进行BFS
- 使用二维数组记录距离
- 定义四个方向的移动：dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1}

  2. BFS实现

    - 从起点开始BFS
- 每次取出队首位置，尝试四个方向
- 对每个可以移动到的新位置：
  * 检查是否越界
  * 检查是否是障碍物
  * 检查是否已访问
  * 更新距离并加入队列

  3. 判断结果

    - 如果到达终点，返回距离
- 如果队列空了还没到达，返回-1

3. 注意事项

  1. 坐标转换：

    • 输入是从1开始的坐标
    • 数组索引从0开始
    • 需要进行转换

  2. 边界检查：

    • 检查是否越界
    • 检查是否是障碍物
    • 检查是否已访问

  3. 优化：

    • 可以用visited数组代替dist数组
    • 可以在找到终点时立即返回

代码

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

struct Point {
    int x, y, step;
    Point(int _x, int _y, int _s) : x(_x), y(_y), step(_s) {}
};

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    int shortestPath(vector<string>& grid, int xs, int ys, int xt, int yt) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        
        queue<Point> q;
        q.push(Point(xs-1, ys-1, 0));  // 坐标转换
        visited[xs-1][ys-1] = true;
        
        while (!q.empty()) {
            Point cur = q.front();
            q.pop();
            
            // 到达终点
            if (cur.x == xt-1 && cur.y == yt-1) {
                return cur.step;
            }
            
            // 尝试四个方向
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                // 检查新位置是否有效
                if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                    && !visited[nx][ny] && grid[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    q.push(Point(nx, ny, cur.step + 1));
                }
            }
        }
        
        return -1;  // 无法到达
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    int xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    
    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    Solution sol;
    cout << sol.shortestPath(grid, xs, ys, xt, yt) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    
    static class Point {
        int x, y, step;
        Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int xs = sc.nextInt() - 1;  // 坐标转换
        int ys = sc.nextInt() - 1;
        int xt = sc.nextInt() - 1;
        int yt = sc.nextInt() - 1;
        
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
        }
        
        // BFS
        boolean[][] visited = new boolean[n][m];
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(xs, ys, 0));
        visited[xs][ys] = true;
        
        int result = -1;
        while (!q.isEmpty()) {
            Point cur = q.poll();
            
            if (cur.x == xt && cur.y == yt) {
                result = cur.step;
                break;
            }
            
            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                    && !visited[nx][ny] && grid[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    q.offer(new Point(nx, ny, cur.step + 1));
                }
            }
        }
        
        System.out.println(result);
    }
}

from collections import deque

def shortest_path(grid, xs, ys, xt, yt):
    n, m = len(grid), len(grid[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 坐标转换
    xs, ys = xs-1, ys-1
    xt, yt = xt-1, yt-1
    
    # BFS
    visited = [[False] * m for _ in range(n)]
    q = deque([(xs, ys, 0)])  # (x, y, steps)
    visited[xs][ys] = True
    
    while q:
        x, y, steps = q.popleft()
        
        if x == xt and y == yt:
            return steps
            
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (0 <= nx < n and 0 <= ny < m 
                and not visited[nx][ny] and grid[nx][ny] == '.'):
                visited[nx][ny] = True
                q.append((nx, ny, steps + 1))
                
    return -1

# 读入数据
n, m = map(int, input().split())
xs, ys, xt, yt = map(int, input().split())
grid = [input() for _ in range(n)]

# 输出结果
print(shortest_path(grid, xs, ys, xt, yt))

算法及复杂度分析

  • 算法：BFS求最短路径
  • 时间复杂度：
    • 每个格子最多访问一次
  • 空间复杂度：
    • 需要距离数组和队列