题解 | #迷宫问题#

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

/*
输入：
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

复制
输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
*/
class Point {
public:
    int x;
    int y;
    int step;
    Point(): x(0), y(0), step(0) {}
    Point(int _x, int _y, int _step): x(_x), y(_y), step(_step) {}
};

int main() {
    int N, M;
    vector<vector<int>> maze;
    vector<vector<bool>> visited;
    vector<vector<vector<int>>> path;
    vector<vector<int>> neighbors = {{0, 1},
                                    {1, 0},
                                    {0, -1},
                                    {-1, 0}};
    while(cin >> N >> M) {
        maze = vector<vector<int>>(N, vector<int>(M, -1));
        visited = vector<vector<bool>>(N, vector<bool>(M, false));
        path = vector<vector<vector<int>>>(N, vector<vector<int>>(M, vector<int>(2, -1)));
        for(int i = 0; i < N; ++i) {
            for(int j = 0; j < M; ++j) {
                cin >> maze[i][j];
            }
        }

        //cout << "input done!" << endl;
        queue<Point> q;
        Point first(0, 0, 0);
        q.push(first);
        visited[0][0] = true;
        int flag = 0;
        int len = 0;
        while(!q.empty()) {
            Point head = q.front();
            if(head.x == N-1 && head.y == M-1) {
                flag = 1;
                len = head.step;
                break;
            }
            for(auto neighbor : neighbors) {
                int x = head.x + neighbor[0];
                int y = head.y + neighbor[1];
                if(x >= 0 && x <= N-1 && y >= 0 && y <= M-1
                  && maze[x][y] == 0 && visited[x][y] == false) {
                      Point tmp(x, y, head.step + 1);
                      visited[x][y] = true;
                      path[x][y] = vector<int>{head.x, head.y};
                      q.push(tmp);
                  }
            }
            q.pop();
        }
        if(flag) {
            vector<vector<int>> res(len + 1, vector<int>(2, 0));
            vector<int> last{N-1, M-1};
            res[len] = vector<int> {N-1, M-1};
            for(int i = 0; i < len; ++i) {
                res[len - i - 1] = path[last[0]][last[1]];
                last = res[len - i - 1];
            }
            for(int i = 0; i < len + 1; ++i) {
                cout << "(" << res[i][0] << "," << res[i][1] << ")" << endl;
            }
        }
        else {
            cout << "error" << endl;
        }
    }
    return 0;
}