题解 | #迷宫问题#

#include <iostream>
#include <tuple>
#include <vector>
#include <list>
using namespace std;

using Puzzle = vector<vector<int>>;
using Path = list<tuple<int,int>>;

bool go(Puzzle& puzzle, Path& path, int x, int y) {
    puzzle[x][y] = 2;
    path.push_back(make_tuple(x, y));

    const auto max_x = puzzle.size() - 1;
    const auto max_y = puzzle[0].size() - 1;
    if (x == max_x && y == max_y) {
        return true;
    }

    // (x-1, y), (x+1, y), (x, y-1), (x, y+1)
    int points[] = {x - 1, y, x + 1, y, x, y - 1, x, y + 1};
    for (int i = 0; i < 8; i += 2) {
        int new_x = points[i];
        int new_y = points[i + 1];
        if (new_x < 0 || new_y < 0
                || new_x > max_x
                || new_y > max_y) {
            continue;
        }
        if (
            puzzle[new_x][new_y] != 1
            && puzzle[new_x][new_y] != 2
        ) {
            if (go(puzzle, path, new_x, new_y)) {
                return true;
            }
        }
    }
    puzzle[x][y] = 0;
    path.pop_back();
    return false;
}

void print_puzzle(const Puzzle& path) {
    for (auto& v1 : path) {
        for (auto& v2 : v1) {
            cout << v2 << " ";
        }
        cout << endl;
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        Puzzle puzzle(n);
        for (size_t i = 0; i < n; ++i) {
            puzzle[i].resize(m);
            for (size_t j = 0; j < m; ++j) {
                cin >> puzzle[i][j];
            }
        }

        Path path;
        go(puzzle, path, 0, 0);
        for (const auto p : path) {
            cout << "(" << get<0>(p) << "," << get<1>(p) << ")" << endl;
        }

    }
}
// 64 位输出请用 printf("%lld")