BFS+回溯

看代码就行啦，很好理解~

#include<iostream>
#include<vector>

using namespace std;
vector<int> drow = {1,0,0,-1};
vector<int> dcol = {0,1,-1,0};
vector<vector<int> > res; 

bool calShorestPath(vector<vector<int> >&grid, int r, int c, int m, int n){
    grid[r][c]=1;
//    cout << "(" << r << "," << c << ")" << endl;
    if(r==m-1&&c==n-1) return true;

    for(int index=0;index<4;index++){
        int nr = r+drow[index];
        int nc = c+dcol[index];
        if(nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==0){
            if (calShorestPath(grid, nr,nc,m,n)){ 
//                cout << "(" << nr << "," << nc << ")" << endl;
                res.insert(res.begin(),{nr,nc});
                return true;
            } 
            grid[nr][nc]=0;
        }
    }
    return false;
}

int main(){
    int m,n;
    while(cin >> m >> n){
        vector<vector<int> > grid(m, vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                cin >> grid[i][j];
            }
        }
        res.clear();
        calShorestPath(grid, 0, 0, m, n);
        cout << "(0,0)" << endl;
        for(auto i : res){
            cout << "(" << i[0] << "," << i[1] << ")" << endl;
        }
    }
    return 0;
}