描述

定义一个二维数组 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、确定DFS后需要确定其三要素：结束条件，何时做选择，何时撤销选择；
3、结束条件：当坐标移动到右下角时，说明已经找到唯一的一条路径，即 
if (x == n - 1 && y == m - 1)
时结束；
4、做选择与撤销选择：
每次当某个方向上的值满足要求（即为0）时，可以做选择，将该坐标加入路径；
加入路径后为了防止该点被重复访问，将该点标记为1；
当沿着该点向上下左右任一方向可以走到终点时，便找到了唯一路径；
若沿着该点向上下左右任一方向全都走不到结束条件，则逐层撤销选择；
即将撤销选择的操作放在上下左右四个遍历的最后，如果某条路径不满足，则会递归一层一层撤销。 

#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 (y-1 >= 0 && 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 (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")