描述

定义一个二维数组 N*M ，如 5 × 5 数组下所示：


int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。

数据范围： 2 \le n,m \le 10 \2≤n,m≤10  ， 输入的内容只包含 0 \le val \le 1 \0≤val≤1 

输入描述：

输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

输出描述：

左上角到右下角的最短路径，格式如样例所示。

示例1

输入： 
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
复制
输出： 
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
复制

示例2

输入： 
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 1
0 1 1 1 0
0 0 0 0 0
复制
输出： 
(0,0)
(1,0)
(2,0)
(3,0)
(4,0)
(4,1)
(4,2)
(4,3)
(4,4)
复制
说明： 
注意：不能斜着走！！

解题思路
1、题目中已经明确说了，只有唯一解，所有从起始点开始，向上下左右四个方向递归遍历即可；
2、递归的结束条件是遍历到右下角的点；
3、在递归的前序遍历位置做选择，即将当前点加入路径（dp.push_back({x, y});），从选择列表里移除（即赋值为1，不可选择）；
4、在递归的后序遍历位置撤销选择，即将当前点从路径移除（dp.pop_back();），同时将当前点重新加入选择列表（还原为0，可被重新选择）；
5、为什么在递归不是在for循环中做的呢？
因为当前可被选择的只有上下左右四个方向，从任一方向执行完后没从结束条件退出的话都会走到撤销选择的地方，回溯进入下一选择分支； 



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

void dfs(int x, int y, int n, int m, vector<vector<int>> &nums, vector<pair<int, int>> &dp) {
    dp.push_back({x, y});//选择该点，即加入路径
    nums[x][y] = 1; //将已经计入路径的点标记为墙壁
    if (x == n - 1 && y == m - 1) {
        for (int i = 0; i < dp.size(); i++) {
            cout << "(" << dp[i].first << "," << dp[i].second << ")" << endl;
        }
        return;
    }
    if (y+1 < m && nums[x][y+1] == 0) {
        dfs(x, y+1, n, m, nums, dp);
    }
    if (x+1 < n && nums[x+1][y] == 0) {
        dfs(x+1, y, n, m, nums, dp);
    }
    if (y-1 >= 0 && nums[x][y-1] == 0) {
        dfs(x, y-1, n, m, nums, dp);
    }
   
    if (x-1 >= 0 && nums[x-1][y] == 0) {
        dfs(x-1, y, n, m, nums, dp);
    }
    dp.pop_back(); // 撤销选择，即从路径中移除
    nums[x][y] = 0; // 恢复为可再次选择状态
}

int main() {
    int n, m;
    while (cin >> n >> m) { 
        vector<vector<int>> nums(n, vector<int>(m, 0));// 注意要先初始化大小才好填值
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> nums[i][j];
            }
        }
        int res = 0;
        vector<pair<int, int>> dp;
        dfs(0, 0, n, m, nums, dp);
    }
}
// 64 位输出请用 printf("%lld")