算法刷题 国赛镜像dfs1题

九宫幻方

题目描述

小明最近在教邻居家的小朋友小学奥数,而最近正好讲述到了三阶幻方这个部分,三阶幻方指的是将 1~9 不重复的填入一个 3*3 的矩阵当中,使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格,在小学奥数里有一句非常有名的口诀:"二四为肩,六八为足,左三右七,戴九履一,五居其中",通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

4 9 2

3 5 7

8 1 6

有意思的是,所有的三阶幻方,都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方(不一定是上图中的那个)中的一些数抹掉,交给邻居家的小朋友来进行还原,并且希望她能够判断出究竟是不是只有一个解。

而你呢,也被小明交付了同样的任务,但是不同的是,你需要写一个程序。

输入描述

输入仅包含单组测试数据。

每组测试数据为一个 3*3 的矩阵,其中为 0 的部分表示被小明抹去的部分。

给出的矩阵至少能还原出一组可行的三阶幻方。

输出描述

如果仅能还原出一组可行的三阶幻方,则将其输出,否则输出"Too Many"(不包含引号)。

输入输出样例

示例

输入

0 7 2
0 5 0
0 3 0

输出

6 7 2
1 5 9
8 3 4

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

代码

#include <bits/stdc++.h>
using namespace std;int n, cnt = 0;
int a[4][4];
int visit[10];
int ans[4][4];
pair<int, int> marker[17];bool check() {int sum = a[1][1] + a[2][2] + a[3][3];int sum1 = a[1][3] + a[2][2] + a[3][1];if (sum1 != sum) return false;for (int i = 1; i <= 3; i++) {int tem1 = 0, tem2 = 0;for (int j = 1; j <= 3; j++) {tem1 += a[i][j];tem2 += a[j][i];}if (tem1 != sum || tem2 != sum) return false;}return true;
}void dfs(int now) {if (now > n) {if (check()) {cnt++;for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)ans[i][j] = a[i][j];}return;}int x = marker[now].first;int y = marker[now].second;for (int i = 1; i <= 9; i++) {if (visit[i]) continue;a[x][y] = i;visit[i] = 1;dfs(now + 1);a[x][y] = 0;visit[i] = 0;}
}int main() {memset(visit, 0, sizeof visit);for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++) {cin >> a[i][j];if (!a[i][j]) marker[++n] = {i, j};visit[a[i][j]] = 1;}dfs(1);if (cnt == 1) {for (int i = 1; i <= 3; i++) {for (int j = 1; j <= 3; j++)cout << ans[i][j] << " ";cout << endl;}} else {cout << -1 << endl;}return 0;
}

镜像类型题目分析 

 分析,这个题目我们可以理解为镜像类型的问题,只要是镜像类型的问题,我们就要计算这个特殊的不同列和行的和是一样的,这样这种题目我们就可以迎刃而解
对于镜像,我们要找原来最初的例子来求行列斜边之间的关系

本题需要注意

我们在使用每一个数字的时候,都需要进行标记,我们使用过的数字就不可以再填写了
我们需要记录每一个点是否填入的状态,填入将不可以再填写
我们使用dfs来解决题目的时候,一定要进行回溯放入最初的值


 

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

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

相关文章

C++:类和对象(从底层编译开始)详解[前篇]

目录 一.inline内联的详细介绍 &#xff08;1&#xff09;为什么在调用内联函数时不需要建立栈帧&#xff1a; &#xff08;2&#xff09;为什么inline声明和定义分离到两个文件会产生链接错误&#xff0c;链接是什么&#xff0c;为什么没有函数地址&#xff1a; 二.类&…

【蓝桥】-动态规划-倒水

目录 一、问题描述​ 二、解题思路 三、完整代码 二维dp 使用滚动数组 一、问题描述 二、解题思路 一个变种的01背包问题&#xff1a; 不选该物品&#xff1a;获得固定收益 e 选择方案1&#xff1a;消耗体积 a&#xff0c;获得价值 b 选择方案2&#xff1a;消耗体积 c&…

【软考网工-实践篇】DHCP 动态主机配置协议

一、DHCP简介 DHCP&#xff0c;Dynamic Host Configuration Protocol&#xff0c;动态主机配置协议。 位置&#xff1a;DHCP常见运行于路由器上&#xff0c;作为DHCP服务器功能&#xff1a;用于自动分配IP地址及其他网络参数给网络中的设备作用&#xff1a;简化网络管理&…

使用 Arduino 和 ThingSpeak 通过互联网进行实时温度和湿度监测

使用 ThingSpeak 和 Arduino 通过 Internet 进行温度和湿度监控 湿度和温度是许多地方(如农场、温室、医疗、工业家庭和办公室)非常常见的测量参数。我们已经介绍了使用 Arduino 进行湿度和温度测量,并在 LCD 上显示数据。 在这个物联网项目中,我们将使用ThingSpeak在互联…

电子电子架构 --- 车载ECU信息安全

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 简单,单纯,喜欢独处,独来独往,不易合同频过着接地气的生活,除了生存温饱问题之外,没有什么过多的欲望,表面看起来很高冷,内心热情,如果你身…

有关Spring 简介和第一个Spring案例:基于XML配置的IoC容器

1.Spirng是什么? Spring 是一个分层的 轻量级开源框架&#xff0c;专为简化企业级Java应用开发而设计。 它由Rod Johnson于2003年提出&#xff0c;核心目标是解决企业应用开发的复杂性&#xff0c;通过 控制反转&#xff08;IoC&#xff09; 和 面向切面编程&#xff08;AOP&…

警惕!Ollama大模型工具的安全风险及应对策略

文章目录 **Ollama的安全隐患&#xff1a;不容忽视的风险****未授权访问&#xff1a;门户洞开的风险****数据泄露&#xff1a;敏感信息的外泄****漏洞利用&#xff1a;历史遗留的隐患** **安全加固&#xff1a;守护数据与服务的防线****限制监听范围&#xff1a;内网隔离的保护…

Qt从入门到入土(十) -数据库操作--SQLITE

认识 数据库是用于存储、管理和检索数据的系统化集合。它是一种按照特定结构组织数据的存储方式&#xff0c;通过软件&#xff08;数据库管理系统&#xff0c;DBMS&#xff09;来实现数据的高效存储、查询、更新和管理。通过文件存储数据适用于少量的数据&#xff0c;而当拥有…

嵌入式2-按键

一、按键 1.原理图&#xff1a; P14按下低电平&#xff0c;不按则高电平。 if((t&(1<<5))!0)& 优先级 8 ! 优先级 7 二、STC89Cxx中文参考手册 1.ram(随机访问存储器&#xff09;易失性 1.1sram&#xff08;512字节&#xff09;静态存储器 2.rom(只读存储…

论文分享 | HE-Nav: 一种适用于复杂环境中空地机器人的高性能高效导航系统

阿木实验室始终致力于通过开源项目和智能无人机产品&#xff0c;为全球无人机开发者提供强有力的技术支持&#xff0c;并推出了开源项目校园赞助活动&#xff0c;助力高校学子在学术研究与技术创新中取得更大突破。近日&#xff0c;香港大学王俊铭同学&#xff0c;基于阿木实验…

平安养老险广西分公司2025年“3∙15”金融消费者权益教育宣传活动暨南湖公园健步行活动

2025年3月11日&#xff0c;由国家金融监督管理总局广西监管局、中国人民银行广西壮族自治区分行指导&#xff0c;平安养老保险股份有限公司&#xff08;以下简称“平安养老险”&#xff09;广西分公司联合平安银行南宁分行、平安人寿广西分公司、平安产险广西分公司、平安证券广…

学习threejs,使用MeshFaceMaterial面材质容器

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️THREE.MeshFaceMaterial 二…

电脑内存不足怎么办?

常规解决方法盘点 关闭后台程序&#xff1a;按下【Ctrl Shift Esc】组合键打开任务管理器&#xff0c;在 “进程” 选项卡里&#xff0c;把当前不用的程序统统 “结束任务” &#xff0c;像那些自动更新的软件、常驻后台的播放器&#xff0c;关了能释放不少内存。比如音乐软…

Excel中国式排名,3种方法!

大家好&#xff0c;我是小鱼。 什么是中国式排名呢&#xff1f; 举个例子比如说公司一共有10名员工进行成绩考核&#xff0c;如果9个人考核成绩都是90分&#xff0c;你是89分&#xff0c;按照国际惯用的排名法则&#xff1a;9 个人考核成绩并列第一&#xff0c;你第10名&…

deepseek+kimi做ppt教程记录

1.首先注册deepseek和kimi deepseek官网&#xff1a;https://chat.deepseek.com/ kimi官网&#xff1a;https://kimi.moonshot.cn/ 以下以一篇工作总结报告为例 2.使用deepseek生成ppt大纲 让deepseek生成kimi生成ppt所需要的内容时&#xff0c;需要注意提示词内容&#xff0c;…

前端无限滚动内容自动回收技术详解:原理、实现与优化

文章目录 一、核心需求与技术挑战1.1 无限滚动的问题症结1.2 自动回收的三大目标 二、技术实现原理2.1 虚拟滚动核心机制2.2 关键技术指标 三、完整实现方案3.1 基础HTML结构3.2 CSS关键样式3.3 JavaScript核心逻辑3.3.1 滚动控制器3.3.2 动态尺寸处理 四、性能优化策略4.1 内存…

【训练细节解读】文本智能混合分块(Mixtures of Text Chunking,MoC)引领RAG进入多粒度感知智能分块阶段

RAG系统在处理复杂上下文时,传统和语义分块方法的局限性,文本分块的质量限制了检索到的内容,从而影响生成答案的准确性。尽管其他算法组件有所进步,但分块策略中的增量缺陷仍可能在一定程度上降低整体系统性能。如何直接量化分块质量?如何有效利用大型语言模型(LLMs)进行…

Jmeter下载及环境配置

Jmeter下载及环境配置 java环境变量配置配置jdk环境变量检查是否配置成功JMeter下载 java环境变量配置 访问地址&#xff1a; https://www.oracle.com/cn/java/technologies/downloads/ 注意&#xff1a;需要自己注册账号 下载完成&#xff0c;解压后的目录为&#xff1a; …

coze ai assistant Task 2

创建一个智能体&#xff1a;夸夸机器人 https://www.coze.cn/store/agent/7480939060010713138?bot_idtrue 改为豆包系列-豆包角色扮演 添加bingWebSearch搜索 添加前&#xff1a; 添加后&#xff1a; 改为工具调用&#xff1a; 添加知识库 使用长期记忆 结合自己的需求&…

Unity基于C#+UGUI解决方案,制作每日签到系统(本地存储签到数据)

一、需求介绍:基于本地存储系统制作一个每日签到系统界面,相关签到界面如下图所示,点击“签到有礼”按钮后就会跳转到“每日登录礼”这个界面,点击“立即签到”按钮之后,按钮就会置灰,而且按钮的文字会变成“等待明日”。 二、制作界面显示相关功能,需要在Unity中新建一…