题解 | #迷宫问题#

迷宫问题

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc

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

int main(){
    int N,M;
    cin>>N>>M;
    int rec[N][M];
    int dir[4][2]={-1,0,1,0,0,-1,0,1};
    int cur;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            cin>>cur;
            rec[i][j]=cur;
        }
    }
    
    stack<pair<int,int>> stk;
    vector<pair<int,int>> res;
    int cur_i,cur_j;
    int p,q;
    cout<<"(0,0)"<<endl;
    stk.push(make_pair(0,0));
    rec[0][0]=-1;
    int flag=false;
    while(!stk.empty() && !flag){
        cur_i=stk.top().first;
        cur_j=stk.top().second;
        stk.pop();
        for(int i=0;i<4;i++){
            p=cur_i+dir[i][0];
            q=cur_j+dir[i][1];
            if(p>=0 && p<N && q>=0 && q<M && rec[p][q]==0){
                stk.push(make_pair(p,q));
                rec[p][q]=-1;
                res.push_back(make_pair(p,q));
                if(p==N-1 && q==M-1){
                    flag=true;
                    break;
                }
            }
        }
    }
    int k=res.size()-2;
    p=N-1;
    q=M-1;
    while(k>=0){
        cur_i=res[k].first;
        cur_j=res[k].second;
        if(abs(p-cur_i)+abs(q-cur_j)!=1){
            res[k]=make_pair(-1,-1);
        }
        else{
            p=cur_i;
            q=cur_j;
        }
        k--;
    }
    for(int i=0;i<res.size();i++){
        if(res[i].first!=-1){
            cout<<"("<<res[i].first<<","<<res[i].second<<")"<<endl;
        }
    }
}
BFS广度优先探索,然后剪枝即可
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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