迷宫寻径问题（BFS最短路）

利用BFS求任意绘制迷宫的路径（感觉路径保存可以再优化下，害(･∀･)！）

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n, m;
int begin_x, begin_y, end_x, end_y;
int room[100][100];//最大为100*100的迷宫大小
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//方向为上左下右
struct node {
    int x, y;
    vector<node> path;//记录路径
};
inline bool CHECK(int x, int y) {//检查是否出界
    return (x < n && x >= 0 && y >= 0 && y < m);
}
vector<node> BFS(int begin_x, int begin_y, int end_x, int end_y) {
    node start, next;
    start.x = begin_x;
    start.y = begin_y;
    start.path.push_back(start);
    queue<node> q;
    q.push(start);
    while (!q.empty()) {
        start = q.front();
        q.pop();
        if (start.x == end_x && start.y == end_y)return start.path;//找到是退出
        for (int i = 0; i < 4; i++) {
            next.x = start.x + dir[i][0];
            next.y = start.y + dir[i][1];
            if (CHECK(next.x,next.y)&&room[next.x][next.y] == 0) {
                room[next.x][next.y] = 1;
                next.path = start.path;
                next.path.push_back(next);
                q.push(next);
            }
        }
    }
}
int main() {
    cout << "请输入迷宫大小（n*m）" << endl;
    cout << "n="; cin >> n;
    cout << "m="; cin >> m;
    cout << "请绘制迷宫" << endl;
    memset(room, 0, sizeof(room));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> room[i][j];
        }
    }
    cout << "请输入起始地x坐标："; cin >> begin_x;
    cout << "请输入起始地y坐标："; cin >> begin_y;
    cout << "请输入目标地x坐标："; cin >> end_x;
    cout << "请输入目标地y坐标："; cin >> end_y;
    vector<node> temp = BFS(begin_x, begin_y, end_x, end_y);
    vector<node>::iterator it;
    for(it=temp.begin();it!=temp.end();++it){
        cout << (*it).x << " " << (*it).y << endl;
    }
    return 0;
}