BFS迷宫最短路径

从起点出发，只能向右、向下、向左、向上移动一个方格，黑色方格为障碍物，不能通过。

求到达终点的最短路径，并输出最短路径。

【输入样例】

5 2 3
0 0 0 1 0
0 0 0 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 1
【输出样例】

<0,0> <0,1> <0,2> <1,2> <1,3> <2,3>
【参考程序】

//小牛编程
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
int adj[105][105];
int visited[105][105];

struct Point {
    int x;
    int y;
    Point *pre;
};

queue<Point *> que;
vector<Point *> path;

int n, endP, endQ;

void bfs(Point *p) {
    que.push(p);
    visited[p->x][p->y] = 1;

    while (!que.empty()) {
        p = que.front();
        path.push_back(p);
        int i = p->x;
        int j = p->y;
        que.pop();

        if (i == endP && j == endQ) {
            return;
        }

        // 4个邻居结点
        if (adj[i][j + 1] == 0 && !visited[i][j + 1] && j + 1 < n) { //向右
            Point *tp = new Point{i, j + 1, path.back()};
            que.push(tp);
            visited[i][j + 1] = 1;
        }

        if (adj[i + 1][j] == 0 && !visited[i + 1][j] && i + 1 < n) { //向下
            Point *tp = new Point{i + 1, j, path.back()};
            que.push(tp);
            visited[i + 1][j] = 1;
        }

        if (adj[i][j - 1] == 0 && !visited[i][j - 1] && j - 1 > 0) { //向左
            Point *tp = new Point{i, j - 1, path.back()};
            que.push(tp);
            visited[i][j - 1] = 1;
        }

        if (adj[i - 1][j] == 0 && !visited[i - 1][j] && i - 1 > 0) { //向上
            Point *tp = new Point{i - 1, j, path.back()};
            que.push(tp);
            visited[i - 1][j] = 1;
        }
    }
}

void visit() {
    vector<Point *> tmpPath;

    Point *endPoint = path[path.size() - 1];
    tmpPath.push_back(endPoint);

    Point *cur = endPoint->pre;
    while (cur != NULL) {
        tmpPath.push_back(cur);
        cur = cur->pre;
    }

    reverse(tmpPath.begin(), tmpPath.end());

    for (int i = 0; i < tmpPath.size(); i++) {
        cout << "<" << tmpPath[i]->x << "," << tmpPath[i]->y << "> ";
    }
}

int main() {
    cin >> n >> endP >> endQ;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> adj[i][j];
        }
    }

    // BFS
    Point *p = new Point{0, 0, NULL}; 
    bfs(p);

    //访问
    visit();

    return 0;
}