题解 | 迷宫问题

#include <bits/stdc++.h>
using namespace std;
class point {
  public:
    int x;
    int y;
    point() {
        x = 0;
        y = 0;
    }
};
bool dfs(int x, int y, int** a, int h, int w,  stack <point>& path, bool** visit
        ) {
    if (x > h - 1)
        return false;
    if (y > w - 1)
        return false;
    if (x < 0)
        return false;
    if (y < 0)
        return false;
    if (a[x][y] == 1)
        return false;
    if (visit[x][y]) {
        return false;
    }
    visit[x][y] = true;
    if (x == h - 1 && y == w - 1) {
        point temp;
        temp.x = x;
        temp.y = y;
        path.push(temp);
        return true;
    }
    if (dfs(x - 1, y, a, h, w, path, visit)) {
        point temp;
        temp.x = x;
        temp.y = y;
        path.push(temp);
        return true;
    }
    if (dfs(x + 1, y, a, h, w, path, visit)) {
        point temp;
        temp.x = x;
        temp.y = y;
        path.push(temp);
        return true;
    }
    if (dfs(x, y - 1, a, h, w, path, visit)) {
        point temp;
        temp.x = x;
        temp.y = y;
        path.push(temp);
        return true;
    }
    if (dfs(x, y + 1, a, h, w, path, visit)) {
        point temp;
        temp.x = x;
        temp.y = y;
        path.push(temp);
        return true;
    }
    visit[x][y] = false;
    return false;
}
int main() {
    int h, w;
    cin >> h >> w;
    int** a = new int* [h];
    bool** visit = new bool *[h];
    stack <point> p;
    queue <point> q;
    for (int i = 0; i < h; ++i) {
        a[i] = new int [w];
        visit[i] = new bool [w];
    }
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            cin >> a[i][j];
            visit[i][j] = false;
        }
    dfs(0, 0, a, h, w, p, visit);
    while(!p.empty()){
        point temp = p.top();
        cout<<"("<<temp.x<<","<<temp.y<<")"<<endl;
        p.pop();
    }
}
// 64 位输出请用 printf("%lld")