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

embedded/2024/11/14 12:58:59/

题目描述

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

相关文章

AI写作(二)NLP:开启自然语言处理的奇妙之旅(2/10)

一、NLP 的基本概念与任务 &#xff08;一&#xff09;自然语言处理的研究对象 自然语言处理&#xff08;NLP&#xff09;处于计算机科学、人工智能和语言学的交叉领域。它所聚焦的人类社会语言信息是无比丰富和复杂的&#xff0c;包括口语、书面语等各种形式。这种语言信息在…

学习笔记——PLCT:milk-v duo(持续更新)

买板子 官方标配有可能是单板&#xff08;如下图&#xff09;无工具包&#xff0c;记得买之前问一下客服。

微软的新模拟器将为 Windows on Arm 带来更多游戏

微软正在测试一项重大的 Windows on Arm 更新&#xff0c;以便让更多 x64 软件和游戏在配备高通 Snapdragon X Elite 或 X Plus 处理器的 Copilot Plus PC 上的 Prism 仿真下运行。 该功能是 Windows 11 Insider Preview Build 27744 的一部分&#xff0c;已向 Canary Channel …

前端Cypress自动化测试全网详解

Cypress 自动化测试详解&#xff1a;从安装到实战 Cypress 是一个强大的端到端&#xff08;End-to-End, E2E&#xff09;功能测试框架&#xff0c;基于 Node.js 构建&#xff0c;支持本地浏览器直接模拟测试&#xff0c;并具有测试录屏功能&#xff0c;极大地方便了测试失败时的…

数字后端教程之Innovus report_property和get_property使用方法及应用案例

数字IC后端实现Innovus中使用report_property可以报告出各种各样object的属性&#xff0c;主要有cell&#xff0c;net&#xff0c;PG Net&#xff0c;Pin&#xff0c;时钟clock&#xff0c;时序库lib属性&#xff0c;Design属性&#xff0c;timing path&#xff0c;timin arc等…

发布一个npm组件库包

Webpack 配置 (webpack.config.js) const path require(path); const MiniCssExtractPlugin require(mini-css-extract-plugin); const CssMinimizerPlugin require(css-minimizer-webpack-plugin); const TerserPlugin require(terser-webpack-plugin);module.exports {…

uniapp中使用原生ajax上传文件并携带其他数据,实时展示上传进度

在uniapp开发过程中&#xff0c;我们经常遇到需要上传文件并携带其他数据的场景。本文将详细介绍如何在uniapp中使用原生ajax实现文件上传&#xff0c;并实时展示上传进度&#xff0c;帮助大家轻松应对此类需求。 一、准备工作 在开始之前&#xff0c;请确保你的uniapp项目已…

python爬虫豆瓣top250

注意 1&#xff0c;BeautifulSoup lxml解析器安装 2&#xff0c;代码缩进格式 f.close() import csvimport requests from bs4 import BeautifulSoup# 请求头部 headers {User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) …