迷宫问题（C++牛客网）

骑猪看日落 2022-11-11 05:27 267阅读 0赞

解题思路：

（1）回溯法，注意值传递而非址传递

#include<iostream>
    #include<vector>
    
    using namespace std;
    void helper(vector<pair<int,int>> mp,vector<vector<int>> &vec,vector<vector<int>> &d,vector<vector<int>> &vis,int x,int y) {
        int m = vec.size(),n=vec[0].size();
        mp.push_back({x,y});
        vis[x][y]=1;
        if(x==m-1 && y==n-1) {
            for(int i=0;i<mp.size();i++) {
                cout<<'('<<mp[i].first<<','<<mp[i].second<<')'<<endl;
            }
            return;
        }
        
        for(int i=0;i<d.size();i++) {
            if(0<=x+d[i][0] && x+d[i][0]<m && 0<=y+d[i][1] && y+d[i][1]<n && vis[x+d[i][0]][y+d[i][1]]==0 && vec[x+d[i][0]][y+d[i][1]]==0) {
                helper(mp,vec,d,vis,x+d[i][0],y+d[i][1]);
            }
        }
        return;
    }
    
    int main() {
        int m,n,a;
        vector<vector<int>> d={
       {1,0},{-1,0},{0,1},{0,-1}};
        while(cin>>m) {
            cin>>n;
            vector<pair<int,int>> mp;
            vector<vector<int>> vec;
            vector<vector<int>> vis(m,vector<int>(n,0));
            for(int i=0;i<m;i++) {
                vector<int> v;
                for(int j=0;j<n;j++) {
                    cin>>a;
                    v.push_back(a);
                }
                vec.push_back(v);
            }
            helper(mp,vec,d,vis,0,0);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，267人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客地下迷宫

小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n\m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍

墨蓝/ 2023年07月25日 15:29/ 0 赞/ 47 阅读

相关等差数列（C++牛客网）

解题思路：（1）数学思想 include<iostream> using namespace std; int helper(

女爷i/ 2022年11月13日 10:29/ 0 赞/ 224 阅读

相关字符串通配符（C++牛客网）

解题思路：（1）使用递归 include<iostream> using namespace std; bool helper

怼烎@/ 2022年11月13日 00:46/ 0 赞/ 245 阅读

相关截取字符串（C++牛客网）

解题思路：（1）substr include<iostream> using namespace std; int main(

亦凉/ 2022年11月12日 01:59/ 0 赞/ 261 阅读

相关迷宫问题（C++牛客网）

解题思路：（1）回溯法，注意值传递而非址传递 include<iostream> include<vector> using names

骑猪看日落/ 2022年11月11日 05:27/ 0 赞/ 268 阅读

相关称砝码（C++牛客网）

解题思路：（1）动态规划，dp\[n\]=去重（dp\[n-1\]+\{dp\}+v\[n\]） include<iostream> include<ve

痛定思痛。/ 2022年11月11日 05:12/ 0 赞/ 231 阅读

相关统计字符（C++牛客网）

解题思路：（1）getline(cin,s)，防止空格的出现 include<iostream> include<map> using

蔚落/ 2022年11月10日 14:57/ 0 赞/ 275 阅读

相关字符串排序（C++牛客网）

解题思路：（1）保存字母并排序（2）将非字母按顺序插入 include<iostream> include<cctype> include<u

矫情吗；*/ 2022年11月09日 12:58/ 0 赞/ 320 阅读

相关合法IP（C++牛客网）

解题思路：（1）判断范围 include<iostream> include<vector> using namespace std;

￡神魔★判官ぃ/ 2022年10月22日 09:23/ 0 赞/ 244 阅读

相关【牛客网】C/C++牛客网专项刷题（04）

以下为牛客网C/C++专项刷题： 1、有以下程序： include <stdio.h> include <string.h> voi

青旅半醒/ 2022年05月18日 04:49/ 0 赞/ 3304 阅读