题解 | #迷宫问题#

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

vector<vector<int>> result;
vector<vector<int>> best_result;
int row;
int column;
vector<vector<int>> input;

void dfs(int begin_row, int begin_col) {
    //判断该结点是否合法
    if (begin_row<0 || begin_row>row-1 || begin_col<0 ||begin_col>column-1 || input[begin_row][begin_col]==1) {
        return;
    }

    //结点合法，加入结点
    input[begin_row][begin_col]=1;
    result.push_back({begin_row,begin_col});

    //找到一个解
    if (begin_row==row-1 && begin_col==column-1) {
        best_result=result;
    }

    dfs(begin_row-1,begin_col);
    dfs(begin_row,begin_col+1);
    dfs(begin_row+1,begin_col);
    dfs(begin_row,begin_col-1);

    input[begin_row][begin_col]=0; //上下左右都走不通的时候，要回溯
    result.pop_back();
}

int main() {
    cin>>row>>column;
    input=vector<vector<int>>(row,vector<int>(column,0)); //初始化，不然只能用push_back添加元素
    for (int i=0; i<row; i++) {
        for (int j=0; j<column; j++) {
            cin>>input[i][j];
        }
    }
    dfs(0,0);

    
    for(vector<vector<int>>::iterator it=best_result.begin();it!=best_result.end();it++) {
            cout<<'('<<(*it)[0]<<','<<(*it)[1]<<')'<<endl;
        }

}