第十五届蓝桥杯C++B组真题-数字接龙

1353 阅读 6 评论 0 点赞

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

##思路
这类问题我们可以用dfs和bfs，由于要记录路径，我这里先考虑的dfs，此题难点我认为是路径不能交叉，即走过的斜线不能和其它斜线交叉，由于本题数据n最大为10我们可以用一个四维数组来存斜线，xie[a][b][c][d]即从(a,b)到(c,d)的斜线，由图可知(x1,y1)到(x2,y2)的另一条斜线为(x1,y2)到(x2,y1),所以明白这点这题就很简单了
**注意注意：此题时间复杂度很大，此代码无法通过所有数据点，具体看评论区**
![](/image_editor_upload/20240415/20240415072424_88081.png)
**参考！参考！参考！参考代码：**
```
#include <bits/stdc++.h>
#define pp ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
using namespace std;
int n,k;
const int N = 30;
int f[N][N];  
string ans;
bool xie[N][N][N][N],ji[N][N];
int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};    //特别注意要按照题目给的要求来，方便后面直接把i当作八个方向的编号 
void dfs(int a,int b,int c,int zong){              //坐标x,y,数,总步数
    if (a==n-1 && b==n-1 && zong==pow(n,2)-1){     //当走到(n-1,n-1),步数为总格子数减一时(左上角一开始的(0,0)不用走)
        if (ans.empty()) cout << -1;               
        for (int i=0;i<zong;i++) cout << ans[i];
        exit(0);                                   //输出完答案直接关闭程序 
    }
    for (int i=0;i<8;i++){
        int x=dx[i]+a,y=dy[i]+b;
        if(f[x][y]==(c+1)%k){
	        if (x>=0 && y>=0 && x<n && y<n && !ji[x][y]){
	        	int lu=0;                            //用来记录用不用走斜线 
	            if (i%2==1){                         //如果走的是斜线需要判断 
	                if(!xie[a][y][x][b]){            //另一条斜线没走过就能走 
	                	lu=1;
	                	xie[a][b][x][y]=true;        
	                	xie[x][y][a][b]=true;
					}
					else continue;                   //与其它交叉就跳过这条路 
	            }
	            ans.push_back(i+'0');
	            ji[x][y] = true;
	            dfs(x, y,(c+1)%k,zong+1);
	            ji[x][y] = false;                    //回溯 
	            ans.pop_back();
	            if(lu & 1){                          //用到斜线的话需要单独回溯 
	                xie[a][b][x][y]=false;
	                xie[x][y][a][b]=false;
	            }
	        }
	    }
    }
}
int main()
{
	pp;                            //用到dfs怕超时，先关一手 
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n;j++) cin >> f[i][j];
    }
    ji[0][0] = 1;                  //不要忘记左上角是默认走过的 
    dfs(0,0,0,0);                  //开始dfs
    cout << -1;                    //还有种情况是当走不到(n-1,n-1)时，输出-1
    return 0;
}
```

0.0分

3 人评分

本文分类：题解列表
浏览次数：1353 次浏览
发布日期：2024-04-15 19:26:22
本文链接：https://blog.dotcpp.com/a/104439

上一篇 > 模拟分布式队列AC
下一篇 > 暴力算法最优解，简单干脆！！！

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

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

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

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

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

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

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

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

评论列表共有 6 条评论

班班最大了 9月前回复TA

@19176722262 那肯定不一样，这个是民间的

19176722262 9月前回复TA

这里的测试数据跟官方的是一样的吗？

班班最大了 9月前回复TA

@smallC233 @dotcpp0665609 我也是这么感觉的，当数据量为6左右就有点超复杂度了，希望这周日的题更好一点，至少不像现在这样

smallC233 9月前回复TA

@smallC233 @dotcpp0607166 我感觉题目话里话外就是要人暴力搜索，但是出题人压根没考虑复杂度，官方应该不存在这样的数据。如果这题是作为搜索练习题无所谓，放在比赛里真的感觉不是很负责，就算能做也远超它本来预期的难度了。

班班最大了 9月前回复TA

@smallC233 好的，正在改进

smallC233 9月前回复TA

hack:
10 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

和

10 2
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0

都是 TLE

第十五届蓝桥杯C++B组真题-数字接龙

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 6 条评论

发表评论 取消回复

评论列表共有 6 条评论

发表评论取消回复