题解 | #迷宫问题#

//https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26pageSize%3D50%26search%3D%26tpId%3D37%26type%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=

#include <iostream>
#include <vector>

using namespace std;

void dfs(int x, int y, vector<pair<int, int>> &st, vector<vector<int>> &num, vector<pair<int, int>> &ans){  //可以设置为全局变量减少def参数
    int n = num.size();
    int m = num[0].size();

    if(x<0||x>(n-1)||y<0||y>(m-1)||num[x][y]==1)
        return;
    else if(x==(n-1)&&y==(m-1)){
        st.push_back(pair<int, int>(x, y));
        ans = st;
        return;
        }else{
            st.push_back(pair<int, int>(x, y)); //可替换为emplace_back()
            num[x][y]=1;
            dfs(x, y+1, st, num, ans);
            dfs(x+1, y, st, num, ans);
            dfs(x, y-1, st, num, ans);
            dfs(x-1, y, st, num, ans);
            st.pop_back();
            num[x][y]=0;
        }
}

int main() {
    int n = 0;
    int m = 0;

    while (cin >> n >> m) {
        vector<vector<int>> num(n, vector<int>(m, 0));
        vector<pair<int, int>> st;
        vector<pair<int, int>> ans;

        for(int i = 0;i<n;i++)
            for(int j = 0;j<m;j++)
                cin >> num[i][j];

        dfs(0, 0, st, num, ans);

        for(auto point:ans)
            cout << '(' << point.first << ',' << point.second << ')' << endl;
//        for(auto [x,y]:ans)
//            cout << '(' << x << ',' << y << ')' << endl;
    }
}