数字接龙(蓝桥杯)

文章目录

  • 数字接龙
    • 【问题描述】
    • 解题思路
    • DFS

数字接龙

【问题描述】

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏,游戏在一个大小为N × N 的格子棋盘上展开,其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下:

  1. 从左上角 (0, 0) 处出发,目标是到达右下角 (N − 1, N − 1) 处的格子,每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
  2. 对于路径经过的棋盘格子,按照经过的格子顺序,上面的数字组成的序列要满足:0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。
  3. 途中需要对棋盘上的每个格子恰好都经过一次(仅一次)。
  4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1),那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。

为了方便表示,我们对可以行进的所有八个方向进行了数字编号,如下图2 所示;因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示,如下图 1是一个迷宫示例,它所对应的答案就是:41255214。
在这里插入图片描述

现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径,输出字典序最小的那一个;如果不存在任何一条路径,则输出 −1。

【输入格式】
第一行包含两个整数 N、K。
接下来输入 N 行,每行 N 个整数表示棋盘格子上的数字。
【输出格式】
输出一行表示答案。如果存在答案输出路径,否则输出 −1。
【样例输入】

3 3
0 2 0
1 1 1
2 0 2

【样例输出】

41255214

【样例说明】
行进路径如图 1 所示。
【评测用例规模与约定】
对于 80% 的评测用例:1 ≤ N ≤ 5。
对于 100% 的评测用例:1 ≤ N ≤ 10,1 ≤ K ≤ 10。

解题思路

题目分析:

  1. 从左上角 (0, 0) 处出发,目标是到达右下角 (N − 1, N − 1) 处的格子,每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
  2. 对于路径经过的棋盘格子,按照经过的格子顺序,上面的数字组成的序列要满足:0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。
  3. 途中需要对棋盘上的每个格子恰好都经过一次(仅一次)。
  4. 如果有多条路径,输出字典序最小的那一个
  5. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1),那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。

解题思路:

  1. 因为题目的数据范围较小,所以可以使用DFS,移动方向为8个方向
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
  1. 我们需要保证遍历顺序为0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . .
g[x][y] == k - 1 && g[tx][ty] == 0) || g[tx][ty] == g[x][y] + 1

g[x][y] == k - 1 && g[tx][ty] == 0 || g[tx][ty] == g[x][y] + 1:这是一个复合条件,用于检查当前格子 (x, y) 的值与目标格子 (tx, ty) 的值之间的关系是否满足游戏规则。具体来说:

  • g[x][y] == k - 1 && g[tx][ty] == 0:如果当前格子的值等于 k - 1(即棋盘上数字的最大值),则目标格子的值必须为 0,这样才能保证数字序列的循环性。
  • ||:逻辑或操作符,用于连接上述条件和下面的条件。两者满足一个即可
  • g[tx][ty] == g[x][y] + 1:如果当前格子的值不是 k - 1,则目标格子的值必须比当前格子的值大 1,这样才能保证数字序列是递增的。
  1. 设置一个cnt,如果cnt=n*n说明遍历了每个位置
  2. 在遍历8个方向时我们按0、1、2、3、4、5、6、7的顺序遍历就能得到最小字典序,并且用path数组保存,就能把路径输出
  3. 只有走对角线才会发生相交,我们设置一个st数组存储到达每个格子的方向,再进行判断
    在这里插入图片描述
if (i == 1 && (st[x - 1][y] == 3 || st[x][y + 1] == 7))continue; // 从当前格子向右移动,检查是否与之前的路径交叉
if (i == 3 && (st[x + 1][y] == 1 || st[x][y + 1] == 5))continue; // 从当前格子向下移动,检查是否与之前的路径交叉
if (i == 5 && (st[x][y - 1] == 3 || st[x + 1][y] == 7))continue; // 从当前格子向左下移动,检查是否与之前的路径交叉
if (i == 7 && (st[x][y - 1] == 1 || st[x - 1][y] == 5))continue; // 从当前格子向左上移动,检查是否与之前的路径交叉

DFS

这段代码是一个基于深度优先搜索(DFS)的算法,用于解决一个特定的路径问题,其中需要考虑路径的字典序。下面是对代码的详细注释:

#include<bits/stdc++.h> // 引入整个标准库和C++ STL库
using namespace std; // 使用标准命名空间int g[11][11]; // 棋盘,存储每个格子的数字
int d[11][11]; // 访问标记,表示当前格子是否已访问
int st[11][11]; // 状态数组,存储到达每个格子的方向
vector<int> path; // 存储最终的路径// 移动方向的偏移量,dx 和 dy 分别表示 x 和 y 轴上的偏移
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};int n, k; // n 是棋盘的大小,k 是棋盘上数字的最大值bool dfs(int x, int y, int cnt) { // 深度优先搜索函数if (x == n - 1 && y == n - 1 && cnt == n * n) // 如果到达棋盘底部的最后一个格子,并且格子数量符合,返回 truereturn true;for (int i = 0; i < 8; i++) { // 遍历所有八个方向int tx = x + dx[i]; // 计算目标x坐标int ty = y + dy[i]; // 计算目标y坐标// 检查目标位置是否在棋盘内,未被访问,并且满足数字序列条件if (tx >= 0 && tx < n && ty >= 0 && ty < n && d[tx][ty] == 0 &&((g[x][y] == k - 1 && g[tx][ty] == 0) || g[tx][ty] == g[x][y] + 1)) {// 检查当前方向是否会导致路径交叉if (i == 1 && (st[x - 1][y] == 3 || st[x][y + 1] == 7))continue; // 从当前格子向右移动,检查是否与之前的路径交叉if (i == 3 && (st[x + 1][y] == 1 || st[x][y + 1] == 5))continue; // 从当前格子向下移动,检查是否与之前的路径交叉if (i == 5 && (st[x][y - 1] == 3 || st[x + 1][y] == 7))continue; // 从当前格子向左下移动,检查是否与之前的路径交叉if (i == 7 && (st[x][y - 1] == 1 || st[x - 1][y] == 5))continue; // 从当前格子向左上移动,检查是否与之前的路径交叉st[x][y] = i; // 记录当前格子的方向d[tx][ty] = 1; // 标记目标格子为已访问path.push_back(i); // 将方向编号添加到路径中if (dfs(tx, ty, cnt + 1)) // 递归搜索下一个位置return true; // 如果找到路径,则返回 truepath.pop_back(); // 回溯,移除路径中的最后一个方向编号d[tx][ty] = 0; // 回溯,重置目标格子的访问标记st[x][y] = -1; // 回溯,重置当前格子的方向}}return false; // 如果所有方向都不是解决方案,则返回 false
}int main() {cin >> n >> k; // 读取棋盘大小和数字的最大值for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> g[i][j]; // 填充棋盘}}// 检查棋盘右下角的数字是否为 k-1,如果不是,则无法形成合法路径,输出-1if (g[n - 1][n - 1] != k - 1) {cout << -1;return 0;}memset(st, -1, sizeof st); // 初始化状态数组,所有值设为 -1d[0][0] = 1; // 标记起始格子为已访问if (dfs(0, 0, 1)) { // 从(0, 0)开始深度优先搜索for (auto i : path) // 输出找到的路径cout << i;} else {cout << -1; // 如果没有找到路径,输出-1}return 0;
}

这段代码使用了深度优先搜索算法来找到一条合法的路径,它考虑了路径的唯一性和循环序列的要求。代码中还包含了避免路径交叉的逻辑。如果找到了一条合法路径,它会输出该路径的编号序列;如果没有找到,它会输出-1。

注意,代码中 memset(st, -1, sizeof st); 用于初始化 st 数组的所有元素为 -1,表示没有格子被访问过。而 d[0][0] = 1; 则是标记起始格子 (0, 0) 为已访问。path 数组用来存储路径,以便在找到解决方案时输出。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/313713.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

游戏发行困境及OgGame云游戏解决方案简述

随着全球化浪潮的持续推进&#xff0c;中国游戏开发者们不再满足于国内市场的发展&#xff0c;而是开始将目光投向更为广阔的海外市场。这一趋势的崛起背后&#xff0c;是中国企业意识到国际化是其发展的必由之路&#xff0c;也是游戏行业突破国内困境的体现。本文将简要阐述游…

【线性代数 C++】求逆矩阵

对于 n n n阶矩阵 A A A&#xff0c;如果有 n n n阶矩阵 B B B&#xff0c;使 A B B A E ABBAE ABBAE&#xff0c;则说 A A A是可逆的&#xff0c;并把 B B B称为 A A A的逆矩阵. A A A的逆矩阵记作 A − 1 A^{-1} A−1&#xff0c;则 B A − 1 BA^{-1} BA−1.若 ∣ A ∣ ≠…

Recommended Azure Monitors

General This document describes the recommended Azure monitors which can be implemented in Azure cloud application subscriptions. SMT incident priority mapping The priority “Blocker” is mostly used by Developers to prioritize their tasks and its not a…

Hive-Sql复杂面试题

参考链接&#xff1a;hive sql面试题及答案 - 知乎 有哪些好的题目都可以给我哦 我来汇总到一起 1、编写sql实现每个用户截止到每月为止的最大单月访问次数和累计到该月的总访问次数 数据&#xff1a; userid,month,visits A,2015-01,5 A,2015-01,15 B,2015-01,5 A,2015-01,…

MySQL面试——聚簇/非聚簇索引

存储引擎是针对表结构&#xff0c;不是数据库 引擎层&#xff1a;对数据层以何种方式进行组织 update&#xff1a;加索引&#xff1a;行级锁&#xff1b;不加索引&#xff1a;表级锁

Java 网络编程之TCP(三):基于NIO实现服务端,BIO实现客户端

前面的文章&#xff0c;我们讲述了BIO的概念&#xff0c;以及编程模型&#xff0c;由于BIO中服务器端的一些阻塞的点&#xff0c;导致服务端对于每一个客户端连接&#xff0c;都要开辟一个线程来处理&#xff0c;导致资源浪费&#xff0c;效率低。 为此&#xff0c;Linux 内核…

Stable Diffusion WebUI 使用 VAE 增加滤镜效果

本文收录于《AI绘画从入门到精通》专栏&#xff0c;专栏总目录&#xff1a;点这里&#xff0c;订阅后可阅读专栏内所有文章。 大家好&#xff0c;我是水滴~~ 本文主要介绍 VAE 模型&#xff0c;主要内容有&#xff1a;VAE 模型的概念、如果下载 VAE 模型、如何安装 VAE 模型、如…

520提升幸福感的好物有哪些?5款必备产品推荐!

520作为年度表白节日&#xff0c;提醒人们别忘了在日常中向所爱之人表达浪漫。从鲜花、美酒到护肤品&#xff0c;礼物成为表达爱意的重要方式。然而&#xff0c;如何选购适合对方的礼物成为人们的难题。过去&#xff0c;关于“硬核520礼物”等话题热度不减&#xff0c;各种送礼…

MQ面试题

为什么要使用消息队列&#xff1f; 优点&#xff1a;解耦、异步、流量削峰 缺点&#xff1a;可用性降低、复杂性提高、一致性问题 为什么选择了RabbitMQ而不是其它的MQ&#xff1f; kafka是以吞吐量高而闻名&#xff0c;不过其数据稳定性一般&#xff0c;而且无法保证消息有…

同旺科技 USB TO SPI / I2C适配器读写24LC256--页写

所需设备&#xff1a; 1、USB 转 SPI I2C 适配器&#xff1b;内附链接 2、24LC256芯片 适应于同旺科技 USB TO SPI / I2C适配器升级版、专业版&#xff1b; 从00地址开始写入64个字节&#xff0c;然后再将64个字节读回&#xff1b; 页写时序&#xff1a; 读时序&#xff1a…

C语言中整型与浮点型在内存中的存储

今天让我们来看看整型的数据和浮点型的数据在内存中是怎么存储的呢 整型数据在内存中的存储 整型数据在内存中存储的是二进制的补码 正数的话也没什么可说的&#xff0c;原码反码补码都相同 我们来看看负数&#xff1a; 以-5为例 原码&#xff1a;10000000 00000000 00000000 0…

Jenkins CI/CD 持续集成专题二 Jenkins 相关问题汇总

一 问题一 pod [!] Unknown command: package 1.1 如果没有安装过cocoapods-packager&#xff0c;安装cocoapods-packager&#xff0c;sudo gem install cocoapods-packager 1.2 如果已经安装cocoapods-packager&#xff0c;还是出现上面的错误&#xff0c;有可能是pod的安…

Spring Boost + Elasticsearch 实现检索查询

需求&#xff1a;对“昵称”进行“全文检索查询”&#xff0c;对“账号”进行“精确查询”。 认识 Elasticsearch 1. ES 的倒排索引 正向索引 对 id 进行检索速度很快。对其他字段即使加了索引&#xff0c;只能满足精确查询。模糊查询时&#xff0c;逐条数据扫描&#xff0c…

vscode ssh远程连接服务器,一直正在下载vscode服务器的解决办法

前言 为方便描述&#xff0c;在本教程中&#xff0c;发起远程连接的叫“主机”&#xff0c;被远程连接的叫“服务器”。 正文 如果主机是首次用vscode远程连接服务器&#xff0c;会在服务器上自动下载vscode服务器&#xff0c;但有时候因为网络问题&#xff0c;会卡在&#xff…

UE4 相机围绕某点旋转

关卡&#xff08;一个相机CameraActor&#xff0c;一个Cube(名叫Target)&#xff09;&#xff1a; 关卡蓝图里的逻辑(为了大家看得清楚&#xff0c;特意连得很紧凑&#xff0c;也比较乱&#xff0c;不然一张截图放不下)&#xff1a; 只对Yaw 只Pitch: 同样对Roll: 围绕任…

switch语句深讲

一。功能 1.选择&#xff0c;由case N:完成 2.switch语句本身没有分支功能&#xff0c;分支功能由break完成 二。注意 1.switch语句如果不加break&#xff0c;在一次判断成功后会执行下面全部语句并跳过判断 2.switch的参数必须是整形或者是计算结果为整形的表达式,浮点数会…

visionTransformer window平台下报错

错误&#xff1a; KeyError: Transformer/encoderblock_0/MlpBlock_3/Dense_0kernel is not a file in the archive解决方法&#xff1a; 修改这个函数即可&#xff0c;主要原因是Linux系统与window系统路径分隔符不一样导致 def load_from(self, weights, n_block):ROOT f&…

c++使用googletest进行单元测试

googletest进行单元测试 使用Google test进行测试一、单元测试二、使用gmock测试 使用Google test进行测试 使用场景&#xff1a; 在平时写代码中&#xff0c;我们需要测试某个函数是否正确时可以使用Google test使用&#xff0c;当然&#xff0c;我们也可以自己写函数进行验证…

云计算时代:SFP、SFP+、SFP28、QSFP+和QSFP28光纤模块详解

随着数据中心的快速发展和云计算的广泛应用&#xff0c;高速、高效率的光纤网络传输成为关键需求。在众多光纤模块中&#xff0c;SFP、SFP、SFP28、QSFP和QSFP28是最常见的几种类型。本文将为您详细解析这几种光纤模块之间的区别&#xff0c;帮助您更好地了解和选择适合自己需求…

网贷大数据黑名单要多久才能变正常?

网贷大数据黑名单是指个人在网贷平台申请贷款时&#xff0c;因为信用记录较差而被列入黑名单&#xff0c;无法获得贷款或者贷款额度受到限制的情况。网贷大数据黑名单的具体时间因个人信用状况、所属平台政策以及银行审核标准不同而异&#xff0c;一般来说&#xff0c;需要一定…