班班最大了

用户名：dotcpp0607166

访问量：7475

签　名：

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

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

　　自我简介：

谢谢大家，让大家见笑了

TA的其他文章

数组的距离
浏览：73

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

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

你可能喜欢

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

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

　　作者: 班班最大了　　　　发表时间：2024-04-15 19:26:22 浏览：1110　|　评论：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分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

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

班班最大了 2024-04-16 13:17:28 |

好的，正在改进

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

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

班班最大了 2024-04-16 15:03:07 |

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

班班最大了

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C语言代码）

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

不容易系列（C语言代码）

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

C语言训练-立方和不等式（C语言代码）

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

评论区

精彩推荐

C语言训练-求素数问题（C语言代码）

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

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

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

字符串输入输出函数（C语言代码）

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

C二级辅导-温度转换（C语言代码）

母牛的故事（C语言代码）

数列问题（C语言代码）

整除的尾数（C语言代码）

班班最大了

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C语言代码）

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

不容易系列 （C语言代码）

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

C语言训练-立方和不等式 （C语言代码）

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

评论区

精彩推荐

C语言训练-求素数问题 （C语言代码）

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

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

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

字符串输入输出函数 （C语言代码）

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

C二级辅导-温度转换 （C语言代码）

母牛的故事 （C语言代码）

数列问题 （C语言代码）

整除的尾数 （C语言代码）

C二级辅导-温度转换（C语言代码）

不容易系列（C语言代码）

C语言训练-立方和不等式（C语言代码）

　　评论区

C语言训练-求素数问题（C语言代码）

字符串输入输出函数（C语言代码）

C二级辅导-温度转换（C语言代码）

母牛的故事（C语言代码）

数列问题（C语言代码）

整除的尾数（C语言代码）