华为机试-迷宫问题（中等）待改

题目描述

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

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

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。
输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。

呃...挖个坑待补充吧，回溯写的还不是很好
没看清题 以为只能向右向下走 用了dfs居然也通过了
看来还是测试样例不够多
如果只考虑向右向下，和二叉树求路径差不多

#include<iostream>
#include<vector>
using namespace std;
bool flag;
void dfs(vector<vector<int>> nums, vector<pair<int, int>>& points, int i, int j) {
    if (flag) return;//已找到路径，return
    if (i >= nums.size() || j >= nums[0].size()) return;//遇到边界return
    points.push_back({ i,j });
    if (nums[i][j] == 1) {//碰到障碍物，此路不通，pop后return
        points.pop_back();
        return;
    }
    if (i == nums.size() - 1 && j == nums[0].size() - 1)//到达终点
    {
        for (auto i : points) {
            cout << '(' << i.first << ',' << i.second << ')' << endl;
        }
        flag = true;
        return;
    }
    dfs(nums, points, i + 1, j);//向右走
    dfs(nums, points, i, j + 1);//向下走
    points.pop_back();//不通，pop
}

int main() {
    int m, n;
    while (cin >> m >> n) {
        vector<vector<int>> nums(m, vector<int>(n, 0));
        vector<pair<int, int>> points;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> nums[i][j];
            }
        }
        flag = false;
        dfs(nums, points, 0, 0);
    }
}