T2077.迷宫最近出口详解

2023-07-27 15:48:39

发布于：河北

29阅读

0回复

0点赞

解决迷宫最短路径问题的一种常用方法是使用广度优先搜索（BFS）算法。以下是解决该问题的一般思路：

定义迷宫的大小和起点、终点的个数。
创建一个队列，用于存储待访问的位置。
创建一个二维数组，用于记录起点到每个位置的最短路径长度。
将起点加入队列，并初始化起点的最短路径长度为0。
开始BFS算法：
从队列中取出一个位置作为当前位置。
如果当前位置是终点，则更新最短路径长度。
遍历当前位置的四个相邻位置：
如果新位置在迷宫范围内且是空地，并且新位置的最短路径长度还未更新，则更新最短路径长度并将新位置加入队列。
输出最短路径的长度。
在实际编码过程中，可能需要根据具体的问题进行适当的修改和调整。例如，可能需要将迷宫的矩阵、起点和终点的坐标作为输入数据读入，或者根据具体要求输出最短路径的具体路径等。

有注释代码

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;

// 定义迷宫的大小
const int MAX_N = 2000;
const int MAX_M = 2000;

// 定义迷宫中的方向
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

// 定义迷宫的状态
const int EMPTY = 0;
const int OBSTACLE = 1;

// 定义迷宫的大小和起点、终点的个数
int n, m;
int startCount, endCount;

// 定义迷宫的矩阵
int maze[MAX_N][MAX_M];

// 定义起点和终点的坐标
vector<pair<int, int>> startPoints;
vector<pair<int, int>> endPoints;

// 定义最短路径的长度
int minSteps = INT_MAX;

// 定义BFS算法求解最短路径
void bfs() {
    // 定义队列用于BFS
    queue<pair<int, int>> q;
    
    // 定义二维数组用于记录起点到每个位置的最短路径长度
    vector<vector<int>> steps(n, vector<int>(m, INT_MAX));
    
    // 将起点加入队列，并初始化起点的最短路径长度为0
    for (int i = 0; i < startCount; i++) {
        q.push(startPoints[i]);
        steps[startPoints[i].first][startPoints[i].second] = 0;
    }
    
    // 开始BFS
    while (!q.empty()) {
        // 取出队首位置
        pair<int, int> cur = q.front();
        q.pop();
        
        // 如果当前位置是终点，则更新最短路径长度
        for (int i = 0; i < endCount; i++) {
            if (cur == endPoints[i]) {
                minSteps = min(minSteps, steps[cur.first][cur.second]);
                break;
            }
        }
        
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            
            // 如果新位置在迷宫范围内且是空地，并且新位置的最短路径长度还未更新，则更新最短路径长度并将新位置加入队列
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == EMPTY && steps[nx][ny] == INT_MAX) {
                steps[nx][ny] = steps[cur.first][cur.second] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}

int main() {
    // 读入迷宫的大小
    cin >> n >> m;
    
    // 读入迷宫的矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }
    
    // 读入起点的个数和坐标
    cin >> startCount;
    for (int i = 0; i < startCount; i++) {
        int x, y;
        cin >> x >> y;
        startPoints.push_back(make_pair(x, y));
    }
    
    // 读入终点的个数和坐标
    cin >> endCount;
    for (int i = 0; i < endCount; i++) {
        int x, y;
        cin >> x >> y;
        endPoints.push_back(make_pair(x, y));
    }
    
    // 使用BFS算法求解最短路径
    bfs();
    
    // 输出最短路径的长度
    cout << minSteps << endl;
    
    return 0;
}

点我答题
无注释代码。~~复制干嘛，愣着呀~~

#include <iostream>
#include <queue>
#include <vector>
#include <climits>

using namespace std;
const int MAX_N = 2000;
const int MAX_M = 2000;


const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int EMPTY = 0;
const int OBSTACLE = 1;


int n, m;
int startCount, endCount;


int maze[MAX_N][MAX_M];


vector<pair<int, int>> startPoints;
vector<pair<int, int>> endPoints;


int minSteps = INT_MAX;

void bfs(){ 
 
    queue<pair<int, int>> q;
    
    
    vector<vector<int>> steps(n, vector<int>(m, INT_MAX));
    
    
    for (int i = 0; i < startCount; i++) {
        q.push(startPoints[i]);
        steps[startPoints[i].first][startPoints[i].second] = 0;
    }
    
    
    while (!q.empty()) {
        
        pair<int, int> cur = q.front();
        q.pop();
        for (int i = 0; i < endCount; i++) {
            if (cur == endPoints[i]) {
                minSteps = min(minSteps, steps[cur.first][cur.second]);
                break;
            }
        }
        
        
        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == EMPTY && steps[nx][ny] == INT_MAX) {
                steps[nx][ny] = steps[cur.first][cur.second] + 1;
                q.push(make_pair(nx, ny));
            }
        }
    }
}

int main() {
    
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
        }
    }
    
    
    cin >> startCount;
    for (int i = 0; i < startCount; i++) {
        int x, y;
        cin >> x >> y;
        startPoints.push_back(make_pair(x, y));
    }
   
    cin >> endCount;
    for (int i = 0; i < endCount; i++) {
        int x, y;
        cin >> x >> y;
        endPoints.push_back(make_pair(x, y));
    }
    bfs();
    cout << minSteps << endl;
    
    return 0;
}