H2230823013

用户名：dotcpp0607166

访问量：5130

签　名：

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

等　　级
排　　名	135
经　　验	7378
参赛次数	2
文章发表	35
年　　龄	3
在职情况	待业
学　　校	贺州学院
专　　业	数据

　　自我简介：

谢谢大家，让大家见笑了

TA的其他文章

愤怒的牛，二分解法
浏览：131

第十五届蓝桥杯C++B组真题-宝石组合
浏览：545

第十五届蓝桥杯C++B组真题-R格式
浏览：213

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

　　作者: H2230823013　　　　发表时间：2024-04-15 19:26:22 浏览：463　|　评论：2　

原题链接：蓝桥杯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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

19176722262

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

2024-04-22 17:04:34

smallC233

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

2024-04-16 12:53:35

H2230823013 2024-04-16 13:17:28 |

好的，正在改进

smallC233 2024-04-16 14:56:28 |

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

H2230823013 2024-04-16 15:03:07 |

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

H2230823013

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

大小写转换（C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

杨辉三角（C语言代码）

【计算球体积】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-最大数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）简单版

文件操作

H2230823013

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-角谷猜想 （C++代码）（3N+1问题）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

大小写转换 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

杨辉三角 （C语言代码）

【计算球体积】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言训练-最大数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）简单版

文件操作

C语言训练-角谷猜想（C++代码）（3N+1问题）

大小写转换（C语言代码）

　　评论区

杨辉三角（C语言代码）

【计算球体积】（C语言代码）

C语言训练-最大数问题（C语言代码）