蓝桥杯试题算法提高学霸的迷宫（精炼代码54行)

系统管理员 2023-01-21 11:17 7阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    const int N = 555;
    int n, m;
    int d[4][2] = {
         {
        1,0},{
        0,-1},{
        0,1},{
        -1,0} };
    int path[N*N*10];
    int dep[N*N*10];
    char e[N][N];
    int S,T;
    char find(int a,int b)//a->b
    {
        
    	if(b-a==1)return 'R';
    	if(b-a==(-1))return 'L';
    	if(b>a)return 'D';
    	return 'U';
    }
    void dfs(int t,int fa)
    {
        
        if(t==0)return ;
        dfs(fa,path[fa]);
        cout<<find(fa,t);
    }
    void bfs(int fir)
    {
        
        memset(path,-1,sizeof(path));
        queue<int> q;
        path[fir]=-2;
        q.push(fir);
        while(q.size())
        {
        
            int t=q.front();
            if(t==T)break;
            q.pop();
            for(int i=0;i<4;i++)
            {
        
                int r=t/m+d[i][0],c=t%m+d[i][1];
                if(r<0||r>=n||c<0||c>=m)continue;
                if(e[r][c]=='1'||path[r*m+c]!=-1)continue;
                path[r*m+c]=t;
                dep[r*m+c]=dep[t]+1;
                q.push(r*m+c);
            }
        }
    
    }
    int main()
    {
        
    	cin >> n >> m;
    	for (int i = 0; i < n; i++)cin >>e[i];
        S=0,T=n*m-1;
    	bfs(S);
    	cout<<dep[T]<<endl;
    	dfs(T,path[T]);
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关蓝桥杯：迷宫

题目描述本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。下图给出了一个迷宫的平面图，其中标记为 11 的为障碍，标记为 00 的为可以通行的

水深无声/ 2024年03月25日 22:24/ 0 赞/ 83 阅读

相关蓝桥杯算法提高学霸的迷宫（bfs+路径记录）

算法提高学霸的迷宫时间限制：1.0s 内存限制：256.0MB 问题描述　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰

小咪咪/ 2024年02月17日 19:40/ 0 赞/ 6 阅读

相关蓝桥杯27-学霸作业

-------------------- title: 蓝桥杯27-学霸作业 date: 2019-11-28 19:11:20 categories: 蓝桥

青旅半醒/ 2023年06月17日 11:52/ 0 赞/ 14 阅读

相关蓝桥杯试题算法提高学霸的迷宫（精炼代码54行)

include<bits/stdc++.h> using namespace std; const int N = 555; int n, m;

系统管理员/ 2023年01月21日 11:17/ 0 赞/ 8 阅读

相关蓝桥杯-算法提高学霸的迷宫（BFS-倒向追踪输出移动方向）

算法提高学霸的迷宫时间限制：1.0s 内存限制：256.0MB 问题描述　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰

不念不忘少年蓝@/ 2022年06月17日 19:59/ 0 赞/ 147 阅读

相关算法提高学霸的迷宫

问题描述　　学霸抢走了大家的作业，班长为了帮同学们找回作业，决定去找学霸决斗。但学霸为了不要别人打扰，住在一个城堡里，城堡外面是一个二维的格子迷宫，要进城堡必须得先通过迷宫

悠悠/ 2022年03月08日 00:56/ 0 赞/ 175 阅读

相关蓝桥杯试题算法提高进制转换

试题算法提高进制转换资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　编写函数将十进制整数按8进制输出，然后编写main函数验证该函数。

约定不等于承诺〃/ 2021年09月24日 00:30/ 0 赞/ 342 阅读

相关蓝桥杯试题算法提高递归输出

试题算法提高递归输出资源限制时间限制：1.0s 内存限制：512.0MB 问题描述　　编写递归函数，将组成整数的所有数字逐个输出，每个数字后面加上一个减

短命女/ 2021年09月24日 00:28/ 0 赞/ 292 阅读

相关蓝桥杯试题算法提高特等奖学金

试题算法提高特等奖学金资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　土豪大学每年都会给学生颁发巨额的特等奖学金，当然，获奖的前提是要

亦凉/ 2021年09月24日 00:26/ 0 赞/ 393 阅读

相关蓝桥杯试题算法提高矩阵转置

试题算法提高矩阵转置资源限制时间限制：1.0s 内存限制：256.0MB 【问题描述】给定一个n×m矩阵相乘，求它的转置。其中1≤n≤20，1≤m≤20，

心已赠人/ 2021年09月24日 00:26/ 0 赞/ 335 阅读