题解 | #迷宫问题#

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
const int N = 110;        // 最大网格尺寸
// 方向数组：右、下、左、上
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

// 全局变量
int mp[N][N];    // 网格地图，0表示可通行，1表示障碍
bool vis[N][N];  // 访问标记数组
int n, m;        // 网格的行数和列数

// 节点结构体
struct node {
    int x, y;    // 节点坐标
    int cnt;     // 到达该节点的步数
};

// 前驱节点结构体
struct pre {
    int x, y;    // 前驱节点的坐标
} pre[N][N];     // 前驱节点数组

// 判断节点是否可通行
bool isPass(int x, int y) {
    // 检查是否在网格范围内、未被访问过且是可通行区域
    return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && mp[x][y] == 0;
}

// 打印从起点到终点的路径
void PrintPath(node end) {
    vector<pair<int, int>> ans;  // 存储路径节点
    int x = end.x, y = end.y;
    
    // 从终点回溯到起点
    while (x != -1 && y != -1) {
        ans.push_back({x, y});
        int px = pre[x][y].x, py = pre[x][y].y;
        x = px, y = py;
    }
    
    // 反转路径，使其从起点到终点
    reverse(ans.begin(), ans.end());
    
    // 打印路径
    for (auto i : ans) {
        cout << "(" << i.first << ',' << i.second << ")" << endl;
    }
    cout << endl;
}

// BFS搜索最短路径
void bfs(node st, node end) {
    queue<node> q;  // BFS队列
    q.push(st);
    vis[st.x][st.y] = true;
    
    // 初始化前驱节点数组
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            pre[i][j] = {-1, -1};
        }
    }
    
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        
        // 到达终点
        if (cur.x == end.x && cur.y == end.y) {
            PrintPath(end);  // 打印路径
            return;
        }
        
        // 探索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dir[i][0];
            int ny = cur.y + dir[i][1];
            
            if (isPass(nx, ny)) {
                q.push({nx, ny, cur.cnt + 1});
                vis[nx][ny] = true;
                pre[nx][ny] = {cur.x, cur.y};  // 记录前驱节点
            }
        }
    }
    
    // 无法到达终点
    cout << -1 << endl;
}

// 主处理函数
void solve() {
    cin >> n >> m;
    
    // 读取网格数据
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
        }
    }
    
    node st = {0, 0, 0};          // 起点
    node end = {n - 1, m - 1, 0};  // 终点
    
    bfs(st, end);  // 执行BFS搜索
}

// 主函数
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t = 1;
    while (t--)solve();
    return 0;
}