题解 | #迷宫问题#

#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int result = INT_MAX;
vector<string> res_path;
void bp(vector<vector<int>> maze, int n, int m ,int i, int j, int count, vector<string> &path, vector<vector<bool>> &used){
    if (i >= n || j >= m || i < 0 || j < 0)
        return;
    if (i == n - 1 && j == m - 1){
        if (result > count){
            result = count;
            res_path = path;
        }   
        return;
    }
    //you
    if (j < m - 1 && maze[i][j + 1] == 0 && !used[i][ j + 1]){
        string tmp = '(' + to_string(i) + ',' + to_string(j + 1) +')';
        used[i][j + 1] = true;
        path.push_back(tmp);
        bp(maze, n, m, i, j + 1, count + 1, path, used);
        path.pop_back();
        used[i][j + 1] = false;
    }
    //shang
    if ( i < n - 1 && maze[i + 1][j] == 0 && !used[i + 1][j]){
        string tmp = '(' + to_string(i + 1) + ',' + to_string(j) +')';
        used[i + 1][j] = true;
        path.push_back(tmp);
        bp(maze, n, m, i + 1, j, count + 1, path, used);
        path.pop_back();
        used[i + 1][j] = false;
    }
    
    //zuo
    if (0 < j && maze[i][j - 1] == 0 && !used[i][j - 1]){
        string tmp = '(' + to_string(i) + ',' + to_string(j - 1) +')';
        path.push_back(tmp);
        used[i][j - 1] = true;
        bp(maze, n, m, i, j - 1, count + 1, path, used);
        path.pop_back();
        used[i][j - 1] = false;
    }
    //xia
    if (0 < i && maze[i - 1][j] == 0 && !used[i - 1][j]){
        string tmp = '(' + to_string(i - 1) + ',' + to_string(j) +')';
        path.push_back(tmp);
        used[i - 1][j] = true;
        bp(maze, n, m, i - 1, j, count + 1, path, used);
        path.pop_back();
        used[i - 1][j] = false;
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    vector<vector<int>> maze(n, vector<int>(m, 0));
    int x;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin>>x;
            maze[i][j] = x;
        }
    }
    vector<vector<bool>> used(n, vector<bool>(m, false));
    vector<string> path;
    path.push_back("(0,0)");
    bp(maze, n, m, 0, 0, 0, path, used);
    for (auto it : res_path)
        cout<< it<<endl;
    //cout << result;
}
// 64 位输出请用 printf("%lld")