题解 | #迷宫问题#

#include <vector>

using namespace std;

/*保证不往回走 dir
   4
2  0  3
   1
*/
//route 存储走过的路径
int next_step(vector<vector<int>> &map, vector<pair<int,int>> route, int x, int y, int dir)
{
    //cout<<y<<x<<" "<<map[y][x]<<endl;
    if(x+1 == map[0].size() && y+1 == map.size()){
        for(int i=0; i<route.size(); i++){
            cout<<"("<<route[i].second<<","<<route[i].first<<")"<<endl;
        }
        return 0;
    }
    
    if(dir != 2 && x+1 < map[0].size() && map[y][x+1] == 0){
        
        route.push_back(make_pair(x+1,y));
        next_step(map, route, x+1, y, 3);
        route.pop_back();
    }
    
    if(dir != 3 && x-1>=0 && map[y][x-1] == 0){
        
        route.push_back(make_pair(x-1,y));
        next_step(map, route, x-1, y, 2);
        route.pop_back();
    }
    
    
    if(dir != 1 && y+1 < map.size() && map[y+1][x] == 0){
        
        route.push_back(make_pair(x,y+1));
        next_step(map, route, x, y+1, 4);
        route.pop_back();
    }
    
    
    if(dir != 4 && y-1>=0 && map[y-1][x] == 0){
        
        route.push_back(make_pair(x,y-1));
        next_step(map, route, x, y-1, 1);
        route.pop_back();
    }

    return 0;
}
int main(void)
{
    int h,w;
    cin>>h>>w;
    
    vector<vector <int> > map(h , vector<int>(w)); 
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++)
            cin>>map[i][j];
    }
        
    
    vector<pair<int,int>> route;
    route.push_back(make_pair(0,0));
    next_step(map, route, 0 ,0, 0);

    return 0;
}