题解C++ | #迷宫问题#

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int input[10][10] = {0};
int vst[10][10] = {0};
vector<pair<int, int>> res;
vector<pair<int, int>> path;

void bfs(int n, int m, int i, int j)
{
    path.push_back(make_pair(i, j));
    input[i][j] = 1;
    if (n-1 == i && m-1 == j)
    {
        res = path;
        return;
    }

    if (i+1 < n && input[i+1][j] == 0) {
        bfs(n, m, i+1, j);
    }
    if (i-1 >= 0 && input[i-1][j] == 0) {
        bfs(n, m, i-1, j);
    }
    if (j+1 < m && input[i][j+1] == 0) {
        bfs(n, m, i, j+1);
    }
    if (j-1 >= 0 && input[i][j-1] == 0) {
        bfs(n, m, i, j-1);
    }

    input[i][j] = 0;
    path.pop_back();
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> input[i][j];


    bfs(n,m,0,0);
    for (int i = 0; i < res.size(); i++)
        cout << "(" << res[i].first << "," << res[i].second << ")" << endl;

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