题解 | #迷宫问题#

可以使用深度搜索DFS来解决迷宫探索问题（广度搜索待研究）

实现DFS可以利用stack，也可以使用递归(本身就是一种压栈方式)。这里使用递归来完成。

设计递归函数时，考虑需要判断每个节点是否在通路上，故返回值定为bool。

而对于每个节点bool值的确定，利用递归进行深度搜索：上、下、左、右四个邻近节点进行探索。当这四个方向节点都不是通路，则说明该节点也不通，状态记为2。

同时，为了避免走重复节点，函数需要记录上一个节点坐标（bef_row, bef_col），防止下一步移动走回去。

遇到的bug：

1. 条件判断时优先判断下一步是否移动回去，再递归判断下一步是否在通路上
2. 判断下一步是否移动回去，row和col不等关系使用||，而不是&&,只要有一个不同即可

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

bool walkMap(vector< vector<int> > & map, int now_row, int now_col, int bef_row, int bef_col, vector<pair<int, int> >& store){
    int len_row = size(map);
    int len_col = size(map[0]);

    if(now_row == len_row-1 && now_col == len_col-1){
        store.push_back(make_pair(now_row, now_col));
        return true;
    }
    else if(now_row >= 0 && now_row < len_row && now_col >= 0 && now_col < len_col 
        && map[now_row][now_col] != 1 && map[now_row][now_col] != 2){
        // map[bef_row][bef_col] = 2;
        
        if((now_row+1 != bef_row || now_col != bef_col)
				 && walkMap(map, now_row+1, now_col, now_row, now_col, store)){
            // cout << "down: " << "(" << now_row << " , " << now_col << ") " << endl;
            store.push_back(make_pair(now_row, now_col));
            return true;
        }else if((now_row-1 != bef_row || now_col != bef_col)
				 && walkMap(map, now_row-1, now_col, now_row, now_col, store)){
            // cout << "up: " << "(" << now_row << " , " << now_col << ") " << endl;
            store.push_back(make_pair(now_row, now_col));
            return true;
        }else if((now_row != bef_row || now_col+1 != bef_col) 
				 && walkMap(map, now_row, now_col+1, now_row, now_col, store)){
            // cout << "right: " << "(" << now_row << " , " << now_col << ") " << endl;
            store.push_back(make_pair(now_row, now_col));
            return true;
        }else if((now_row != bef_row || now_col-1 != bef_col) 
				 && walkMap(map, now_row, now_col-1, now_row, now_col, store)){
            // cout << "left: " << "(" << now_row << " , " << now_col << ") " << endl;
            store.push_back(make_pair(now_row, now_col));
            return true;
        }else{
            map[now_row][now_col] = 2;
            return false;
        }
    }else{  
        return false;
    }
}

int main() {
    int row, col = 0;
    cin >> row >> col;

    vector< vector<int> > map;

    for(int i = 0; i < row; i ++){
        vector<int> vec_row(col, 0);
        for(int j = 0; j < col; j ++){
            int val = 0;
            cin >> val;
            vec_row[j] = val;
        }
        map.push_back(vec_row);
    }

    vector<pair<int, int> > store;
    if(walkMap(map, 0, 0, 0, 0, store)){
        // printf("(0,0)\n");
        for(int i = 0; i < size(store); i ++){
            int row = store[size(store)-i-1].first;
            int col = store[size(store)-i-1].second;

            printf("(%d,%d)\n", row, col);
        }
        // printf("(%d,%d)\n", row-1, col-1);
    }
}
// 64 位输出请用 printf("%lld")