蓝桥杯2024年第十五届省赛真题-数字接龙dfs

1249 阅读 2 评论 2 点赞

原题链接：蓝桥杯2024年第十五届省赛真题-数字接龙

#include<bits/stdc++.h>
    using namespace std;
    const int N=11;
    
    int n,k;
    int g[N][N];//初始化输入的矩阵
    int dx[]={-1,-1,0,1,1,1,0,-1};
    int dy[]={0,1,1,1,0,-1,-1,-1};//y总视频有介绍为什么这么排
    
    string path;//答案
    bool st[N][N];//标注是否走过
    int edge[N][N][N][N];//edge[x1][y1][x2][y2]表示从(x1,y1)走到(x2,y2)
    
    bool dfs(int a,int b)
    {
        //每个格子恰好都经过一次（仅一次）
        if(a==n-1&&b==n-1) return path.size()==n*n - 1;//到终点并正好走的步数够
        st[a][b]=true;
        
        for(int i=0;i<8;i++)
        {
            int x=a+dx[i],y=b+dy[i];
            if(x<0||x>=n||y<0||y>=n) continue;//越界
            if(st[x][y]) continue;//已访问过
            if(g[x][y]!=(g[a][b]+1)%k) continue;//012,下一个数是上一个数+1循环
            //(i%2)斜着走;(a,b)->(x,y)或者(x,y)->(a,b)已经走过为true
            if(i%2&&(edge[a][y][x][b]||edge[x][b][a][y])) continue;//交叉路径
            
            edge[a][b][x][y]=true;
            path+=i+'0';//加入结果的字符串中
            
            if(dfs(x,y)) return true;
            
            path.pop_back();//恢复现场
            edge[a][b][x][y]=false;
        }
        st[a][b]=false;
        return false;
    }
    
    int main()
    {
        cin>>n>>k;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>g[i][j];
        
        if(!dfs(0,0)) cout<<-1<<endl;
        else cout<<path<<endl;
        
        return 0;
    }

0.0分

2 人评分

本文分类：题解列表
浏览次数：1249 次浏览
发布日期：2025-02-21 20:30:27
本文链接：https://blog.dotcpp.com/a/108535

上一篇 > 进制练习之十六进制转八进制C++/乱搞
下一篇 > 明明的随机数（使用unordered_set和sort）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2024年第十五届省赛真题-数字接龙dfs

评论列表共有 2 条评论

发表评论取消回复

蓝桥杯2024年第十五届省赛真题-数字接龙dfs

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 2 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 2 条评论

发表评论取消回复