第十五届蓝桥杯C/C++B组题解——数字接龙

题目描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏,游戏在一个大小为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

代码:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 15;
int path[N][N];int n, k;
bool st[N * N][N * N];
string h;//分别对应图二中的八个方向
int dx[8] = { -1,-1,0,+1,+1,+1,0,-1 };
int dy[8] = {0,+1,+1,+1,0,-1,-1,-1};
//去记录对角线
bool dg[N][N][N][N];
bool dfs(int x,int y)
{//说明已经走到了最后if (x == n-1 && y == n-1) return h.size() != n * n -1;st[x][y] = true;//对八个方向都进行判断for (int i = 0; i < 8; i++){//获得进行过操作之后的点的坐标int a = x + dx[i];int b = y + dy[i];//判断该点是否都合法//超过棋盘范围   if (a < 0 || a >= n || b < 0 || b >= n) continue;//该点不是上一个点+1  if (path[a][b] !=  (path[x][y] + 1 ) % k) continue;//这个点不是第一次被访问到if (st[a][b] == true) continue;//斜对角线不能存在值//只有斜着的才要去判断  1,3,5,7方向if (i % 2 == 1 && (dg[x][b][a][y] == true || dg[a][y][x][b] == true)) continue;//以上条件全部都满足  则//存入字典序h += i + '0';dg[x][y][a][b] = true;dfs(a,b);dg[x][y][a][b] = false;h.pop_back();}st[x][y] = true;return false;}
int main()
{cin >> n >> k;//存入整个棋盘for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> path[i][j];if (dfs(0, 0)) cout << h << endl;else printf("-1");return 0;
}

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

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

相关文章

得物多模态大模型在重复商品识别上的应用和架构演进

重复商品治理介绍 根据得物的平台特性&#xff0c;同一个商品在平台上不能出现多个链接&#xff0c;原因是平台需要保证一品一链的特点&#xff0c;以保障商品的集中竞价&#xff0c;所以说一个商品在整个得物平台上只能有一个商详链接&#xff0c;因此我们需要对一品多链的情…

盘点2024年惊艳的10款录屏工具!!

你是否经常需要捕捉电脑屏幕上的精彩瞬间&#xff1f;或者想要记录自己操作某个应用程序的流程&#xff1f;这时候你就需要一款录屏工具啦&#xff01;在学习、工作和娱乐中&#xff0c;录屏工具都能成为你的得力助手。无论你是做教学视频、游戏解说还是分享精彩瞬间&#xff0…

vue+websocket实现即时聊天平台

目录 1 什么是websocket 2 实现步骤 2.1 导入依赖 2.2 编写代码 1 什么是websocket WebSocket 是一种在单个 TCP 连接上进行全双工通信的协议。它主要用于在客户端和服务器之间建立持久的连接&#xff0c;允许实时数据交换。WebSocket 的设计目的是为了提高 Web 应用程序的…

软件设计师-上午题-15 计算机网络(5分)

计算机网络题号一般为66-70题&#xff0c;分值一般为5分。 目录 1 网络设备 1.1 真题 2 协议簇 2.1 真题 3 TCP和UDP 3.1 真题 4 SMTP和POP3 4.1 真题 5 ARP 5.1 真题 6 DHCP 6.1 真题 7 URL 7.1 真题 8 浏览器 8.1 真题 9 IP地址和子网掩码 9.1 真题 10 I…

C++:map 和 set 的使用

前言 平衡二叉搜索树 ( AVL树 ) 由于二叉搜索树在特殊情况下&#xff0c;其增删查的效率会降低到 O ( N )&#xff0c;因此对二叉搜索树进行改良&#xff0c;通过旋转等方式将其转换为一个左右均衡的二叉树&#xff0c;这样的树就称为平衡二叉搜索树&#xff0c;又称 AVL树。…

Vue 自定义icon组件封装SVG图标

通过自定义子组件CustomIcon.vue使用SVG图标&#xff0c;相比iconfont下载文件、重新替换更节省时间。 子组件包括&#xff1a; 1. Icons.vue 存放所有SVG图标的path 2. CustomIcon.vue 通过icon的id索引对应的图标 使用的时候需要将 <Icons></Icons> 引到使用的…

面相小白的php反序列化漏洞原理剖析

前言 欢迎来到我的博客 个人主页:北岭敲键盘的荒漠猫-CSDN博客 本文整理反序列化漏洞的一些成因原理 建议学习反序列化之前 先对php基础语法与面向对象有个大体的了解 (我觉得我整理的比较细致&#xff0c;了解这俩是个啥就行) 漏洞实战情况 这个漏洞黑盒几乎不会被发现&am…

ReactPress:深入解析技术方案设计与源码

ReactPress Github项目地址&#xff1a;https://github.com/fecommunity/reactpress 欢迎提出宝贵的建议&#xff0c;欢迎一起共建&#xff0c;感谢Star。 ReactPress是一个基于React框架开发的开源发布平台&#xff0c;它不仅仅是一个简单的博客系统&#xff0c;更是一个功能全…

canal1.1.7使用canal-adapter进行mysql同步数据

重要的事情说前面&#xff0c;canal1.1.8需要jdk11以上&#xff0c;大家自行选择&#xff0c;我这由于项目原因只能使用1.1.7兼容版的 文章参考地址&#xff1a; canal 使用详解_canal使用-CSDN博客 使用canal.deployer-1.1.7和canal.adapter-1.1.7实现mysql数据同步_mysql更…

SpringBoot之定时任务

1. 前言 本篇博客是个人的经验之谈&#xff0c;不是普适的解决方案。阅读本篇博客的朋友&#xff0c;可以参考这里的写法&#xff0c;如有不同的见解和想法&#xff0c;欢迎评论区交流。如果此篇博客对你有帮助&#xff0c;感谢点个赞~ 2. 场景 我们讨论在单体项目&#xff0c…

绿色能源发展关键:优化风电运维体系

根据QYResearch调研团队最新发布的《全球风电运维市场报告2023-2029》显示&#xff0c;预计到2029年&#xff0c;全球风电运维市场的规模将攀升至307.8亿美元&#xff0c;并且在接下来的几年里&#xff0c;其年复合增长率&#xff08;CAGR&#xff09;将达到12.5%。 上述图表及…

前端 Canvas 绘画 总结

目录 一、使用案例 1、基础使用案例 2、基本案例改为直接JS实现 二、相关资料 1、API教程文档 2、炫酷案例 一、使用案例 1、基础使用案例 使用Canvas的基本步骤&#xff1a; 1、需要一个canvas标签 2、需要获取 画笔 对象 3、使用canvas提供的api进行绘图 <!--…

力扣排序455题(分发饼干)

假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。 但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i],这是能 让孩子们满足胃口的饼干的最小尺寸;并且每块饼 干j&#xff0c;都有一个尺寸 s[j]。如果 s[j]> g[i]&…

C语言 | Leetcode C语言题解之第537题复数乘法

题目&#xff1a; 题解&#xff1a; bool parseComplexNumber(const char * num, int * real, int * image) {char *token strtok(num, "");*real atoi(token);token strtok(NULL, "i");*image atoi(token);return true; };char * complexNumberMulti…

Android使用scheme方式唤醒处于后台时的App场景

场景&#xff1a;甲App唤醒处于后台时的乙App的目标界面Activity&#xff0c;且乙App的目标界面Activity处于最上层&#xff0c;即已经打开状态&#xff0c;要求甲App使用scheme唤醒乙App时&#xff0c;达到跟从桌面icon拉起App效果一致&#xff0c;不能出现只拉起了乙App的目标…

如何对接低价折扣相对稳定电影票渠道?

对接低价折扣电影票渠道需要经过一系列步骤&#xff0c;以确保能够为用户提供优惠且可靠的购票体验。以下是一个基本的对接流程&#xff1a; 1.市场调研&#xff1a; 调研市场上的电影票销售渠道&#xff0c;了解主要的电影票批发商和分销商。分析竞争对手的折扣电影票服务&a…

【上云拼团Go】如何在腾讯云双十一活动中省钱

1. 前言 双十一已经成为了全球最大的购物狂欢节&#xff0c;除了电商平台的优惠&#xff0c;云计算服务商也纷纷在这个期间推出了诱人的促销活动。腾讯云作为中国云计算的领军企业之一&#xff0c;每年双十一的活动都吸引了大量开发者、企业和个人用户参与。那么&#xff0c;在…

新能源企业在精益变革过程中可能会遇到哪些困难?

在绿色转型的浪潮中&#xff0c;新能源企业作为推动社会可持续发展的先锋力量&#xff0c;正加速迈向精益化管理的新阶段。然而&#xff0c;这条变革之路并非坦途&#xff0c;而是布满了未知与挑战。本文&#xff0c;天行健王春城老师将深入探讨新能源企业在精益变革过程中可能…

Maven的安装配置

文章目录 一、MVN 的下载二、配置maven2.1、更改maven/conf/settings.xml配置2.2、配置环境变量一、MVN 的下载 还是那句话,要去就去官网或者github,别的地方不要去下载。我们下载binaries/ 目录下的 cd /opt/server wget https://downloads.apache.org/maven/maven-3/3.9.6/…

OpenCV视觉分析之目标跟踪(10)估计两个点集之间的刚性变换函数estimateRigidTransform的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 计算两个2D点集之间的最优仿射变换 estimateRigidTransform 是 OpenCV 中的一个函数&#xff0c;用于估计两个点集之间的刚性变换&#xff08;即…