C++迷宫问题 DFS

迷宫问题

http://www.nowcoder.com/questionTerminal/cf24906056f4488c9ddb132f317e03bc

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

int row = 0, col = 0;
vector<vector<int> > vec;
vector<pair<int, int> > ans;
vector<pair<int, int> > temp;
void dfs(int a, int b)
{
    temp.push_back({a, b});
    vec[a][b] = 1;
    if(a == row - 1 && b == col - 1)
    {
        ans = temp;
        return ;
    }

    if(a - 1 >= 0 && vec[a - 1][b] == 0 ) dfs(a - 1, b);//上
    if(a + 1 <= row - 1 && vec[a + 1][b] == 0 ) dfs(a + 1, b);//下
    if(b - 1 >= 0 && vec[a][b - 1] == 0 ) dfs(a, b - 1);//左
    if(b + 1 <= col - 1 && vec[a][b + 1] == 0 ) dfs(a, b + 1);//右

    vec[a][b] = 0;
    temp.pop_back();
}
int main(int argc, char* argv[])
{


    while(cin >> row >> col)
    {
        for(int i = 0; i < row; ++i)
        {
            vector<int> temp;
            for(int j = 0; j < col; ++j)
            {
                int val = 0;
                cin >> val;
                temp.push_back(val);
            }
            vec.push_back(temp);
        }

        dfs(0, 0);
        for(auto c : ans)
        {
            cout << "(" << c.first << "," << c.second << ")" << endl;
        }
        vec.clear();
        ans.clear();
        temp.clear();
    }

    return 0;
}
全部评论
能保证是最短的路径嘛?
点赞 回复 分享
发布于 2021-09-05 15:12
大佬,用题目给的实例1作为测试用例,似乎不通过。。。
点赞 回复 分享
发布于 2021-03-30 11:13
大神请教下,dfs函数里push_back后vec[a][b] = 1及最后vec[a][b] = 0目的是啥啊,没捋清楚。
点赞 回复 分享
发布于 2021-03-29 17:31

相关推荐

Jcwemz:中软证书写单行,考了什么学了什么相关技术栈的内容就说自己会什么, 没实习就包装实习简历,将项目经历写成实习做的,项目时间拉长,项目成果具体化,测试的项目成果无非就是写了多少用例查出了多少bug,重要的不是实习了多久,而是你会多少东西,你能表达的就都是你的。 cet4,随便找个地方标上就好了,不用写单行。 粗略建议,我也不在行,觉得对的可以采纳
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务