当前位置: 首页 > news >正文

1 月 26日算法练习

文章目录

  • 九宫幻方
  • 穿越雷区
  • 走迷宫

九宫幻方

小明最近在教邻居家的小朋友小学奥数,而最近正好讲述到了三阶幻方这个部分,三阶幻方指的是将1~9不重复的填入一个33的矩阵当中,使得每一行、每一列和每一条对角线的和都是相同的。
三阶幻方又被称作九宫格,在小学奥数里有一句非常有名的口诀:“二四为肩,六八为足,左三右七,戴九履一,五居其中”,通过这样的一句口诀就能够非常完美的构造出一个九宫格来。
4 9 2
3 5 7
8 1 6
有意思的是,所有的三阶幻方,都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方(不一定是上图中的那个)中的一些数抹掉,交给邻居家的小朋友来进行还原,并且希望她能够判断出究竟是不是只有一个解。
而你呢,也被小明交付了同样的任务,但是不同的是,你需要写一个程序~
【输入格式】
输入仅包含单组测试数据。
每组测试数据为一个3
3的矩阵,其中为0的部分表示被小明抹去的部分。
对于100%的数据,满足给出的矩阵至少能还原出一组可行的三阶幻方。

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

【样例输入】

0 7 2
0 5 0
0 3 0
【样例输出】

6 7 2
1 5 9
8 3 4

思路:dfs,回溯

#include<iostream>
#include<utility>using namespace std;int a[5][5],ans[5][5];
pair<int, int> p[10];
int n,cnt;
int vis[10];int check(){int sum = a[1][1]+a[2][2]+a[3][3];if(sum!=a[1][3]+a[2][2]+a[3][1])return 0;for(int i=1;i<=3;i++){int tmp1=0,tmp2=0;for(int j=1;j<=3;j++){tmp1+=a[i][j],tmp2+=a[j][i];}if(sum!=tmp1||sum!=tmp2)return 0;}return 1;
}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 = p[now].first,y = p[now].second;for(int k=1;k<=9;k++){if(vis[k])continue;a[x][y] = k;vis[k] = 1;dfs(now + 1);a[x][y]=0;vis[k]=0;}}int main( ){for(int i=1;i<=3;i++){for(int j=1;j<=3;j++){cin>>a[i][j];if(!a[i][j])p[++n] = make_pair(i, j);vis[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]<<" \n"[j==3];}}}else cout<<"Too Many\n";return 0;
}

穿越雷区

X 星的坦克战车很奇怪,它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转,否则将报废。
某坦克需要从 A 区到 B 区去(A,B 区本身是安全区,没有正能量或负能量特征),怎样走才能路径最短?
已知的地图是一个方阵,上面用字母标出了 A,B 区,其它区都标了正号或负号分别表示正负能量辐射区。
例如:

A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能在水平或垂直方向上移动到相邻的区。
输入格式

输入第一行是一个整数n,表示方阵的大小, 4 ≤ n < 100。
接下来是n 行,每行有n 个数据,可能是 A,B,+,- 中的某一个,中间用空格分开。
A,B 都只出现一次。
输出格式

要求输出一个整数,表示坦克从A区到B区的最少移动步数。如果没有方案,则输出-1
样例输入

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

样例输入
10
dfs,剪枝

#include<iostream>
#include<utility>
using namespace std;
const int N = 1e3 + 5;
int n,ans;
pair<int,int> st,ed;
int a[N][N],vis[N][N];void dfs(int x,int y,int cnt){if(cnt>ans)return;if(cnt>vis[x][y])return;if(x>n||x<1||y<1||y>n)return;if(x==ed.first&&y==ed.second){ans=cnt;return;}vis[x][y]=cnt;int nx = x-1,ny=y;if(a[nx][y]!=a[x][y])dfs(nx,ny,cnt+1);nx = x+1,ny=y;if(a[nx][y]!=a[x][y])dfs(nx,ny,cnt+1);nx = x,ny = y-1;if(a[x][ny]!=a[x][y])dfs(nx,ny,cnt+1);nx = x,ny = y+1;if(a[x][ny]!=a[x][y])dfs(nx,ny,cnt+1);
}int main(){char x;cin>>n;ans = 0x3f3f3f3f;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=0x3f3f3f3f;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>x;if(x=='A')st.first=i,st.second=j,a[i][j]=-1;else if(x=='B')ed.first=i,ed.second=j,a[i][j]=-1;else if(x=='+')a[i][j]=1;else a[i][j]=0;}}dfs(st.first,st.second,0);cout<<ans<<'\n';return 0;
}

走迷宫

给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0 或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。

最初,有一个人位于左上角 (1,1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问,该人从左上角移动至右下角 (n,m) 处,至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0,且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行,每行包含 m 个整数(0 或 1),表示完整的二维数组迷宫。

输出格式

输出一个整数,表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例:

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例:

8

  • bfs
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
using PII = pair<int,int>;
const int N = 1e2+5;
int w,h;
int mp[N][N],ans[N][N];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void bfs(){queue<pair<int,int>> q;q.push({0,0});memset(ans,-1,sizeof(ans));ans[0][0] = 0;while(!q.empty()){PII front = q.front();q.pop();for(int k=0;k<4;k++){int nx=dx[k]+front.first,ny=dy[k]+front.second;if(nx>=0&&nx<w&&ny>=0&&ny<h&&ans[nx][ny]==-1&&mp[nx][ny]==0){ans[nx][ny]=ans[front.first][front.second]+1;q.push({nx,ny});}}}
}int  main( ){cin>>w>>h;for(int i=0;i<w;i++)for(int j=0;j<h;j++)cin>>mp[i][j];bfs();cout<<ans[w-1][h-1]<<'\n';return 0;
}

相关文章:

1 月 26日算法练习

文章目录 九宫幻方穿越雷区走迷宫 九宫幻方 小明最近在教邻居家的小朋友小学奥数&#xff0c;而最近正好讲述到了三阶幻方这个部分&#xff0c;三阶幻方指的是将1~9不重复的填入一个33的矩阵当中&#xff0c;使得每一行、每一列和每一条对角线的和都是相同的。 三阶幻方又被称…...

今日AI大热潮,明日智能风向标

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

03 SB实战 -微头条之首页门户模块(跳转某页面自动展示所有信息+根据hid查询文章全文并用乐观锁修改阅读量)

1.1 自动展示所有信息 需求描述: 进入新闻首页portal/findAllType, 自动返回所有栏目名称和id 接口描述 url地址&#xff1a;portal/findAllTypes 请求方式&#xff1a;get 请求参数&#xff1a;无 响应数据&#xff1a; 成功 {"code":"200","mes…...

Abaqus许可分析工具

在当今的知识产权保护和许可管理领域&#xff0c;一款高效、精准的许可分析工具对于企业来说至关重要。Abaqus许可分析工具凭借其强大的功能和卓越的性能&#xff0c;成为了企业优化知识产权许可管理的得力助手。 一、Abaqus许可分析工具的核心优势 1.全面性&#xff1a;Abaqus…...

【开发工具】从eclipse到idea的过度

背景 随着eclipse相比以前性能慢了不少&#xff0c;idea在开发工具领域越战越猛&#xff0c;市场份额也逐年增加&#xff0c;其体验得了软件工程师的热爱。 概要 本文只是做了一个简要的记录&#xff0c;简单描述下本人从eclipse到idea的过度的心态。 正文 在大厂都会研发自…...

【QT+QGIS跨平台编译】之十一:【libzip+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、libzip介绍二、文件下载三、文件分析四、pro文件五、编译实践一、libzip介绍 libzip是一个开源C库,用于读取,创建和修改zip文件。 libzip可以从数据缓冲区,文件或直接从其他zip归档文件直接复制的压缩数据中添加文件。在不关闭存档的情况下所做的更改可以还原…...

openlayers+vue实现缓冲区

文章目录 前言一、准备二、初始化地图1、创建一个地图容器2、引入必须的类库3、地图初始化4、给地图增加底图 三、创建缓冲区1、引入需要的工具类库2、绘制方法 四、完整代码总结 前言 缓冲区是地理空间目标的一种影响范围或服务范围,是对选中的一组或一类地图要素(点、线或面…...

(大众金融)SQL server面试题(3)-客户已用额度总和

今天&#xff0c;面试了一家公司&#xff0c;什么也不说先来三道面试题做做&#xff0c;第三题。 那么&#xff0c;我们就开始做题吧&#xff0c;谁叫我们是打工人呢。 题目是这样的&#xff1a; DEALER_INFO经销商授信协议号码经销商名称经销商证件号注册地址员工人数信息维…...

c语言笔记

1. c语言部分算法列举 1.1 找数 二分查找&#xff08;前提是数据必须有序&#xff09; 1.2 求极值 1.3 数组逆序 1.4 排序法&#xff08;***重点***&#xff09; 1.4.1 选择排序法 1.4.2 冒泡排序法 1.4.3 插入排序法 2. 字符型数组 2.1 使用格式 char s[10]; …...

6轴机器人运动正解-逆解控制【1】——三种控制位姿的方式

概览&#xff1a; 通过运动学正解控制机器人运动通过运动学逆解控制机器人运动一个简单的物体搬运&#xff08;沿轨迹运动&#xff09; 后续会陆续更新&#xff08;本例仅供学习交流用&#xff09; 一、6轴机器人 二、运动正解控制 通过修改各个轴的角度&#xff0c;实现末…...

c# Microsoft UI Automation

Microsoft UI Automation&#xff08;UIA&#xff09;是一种用于自动化Windows应用程序用户界面&#xff08;UI&#xff09;的框架。它允许开发人员编写自动化测试脚本、辅助技术应用程序和其他需要与应用程序交互的工具。以下是一些关于Microsoft UI Automation的重要信息&…...

C#-前后端分离连接mysql数据库封装接口

C#是世界上最好的语言 新建项目 如下图所示选择框红的项目 然后新建 文件夹 Common 并新建类文件 名字任意 文件内容如下 因为要连接的是mysql数据库 所以需要安装 MySql.Data.MySqlClient 依赖; using MySql.Data.MySqlClient; using System.Data;namespace WebApplication1.…...

yolov8 opencv dnn部署自己的模型

源码地址 本人使用的opencv c github代码,代码作者非本人 使用github源码结合自己导出的onnx模型推理自己的视频 推理条件 windows 10 Visual Studio 2019 Nvidia GeForce GTX 1070 opencv4.7.0 (opencv4.5.5在别的地方看到不支持yolov8的推理&#xff0c;所以只使用opencv…...

插槽(64-67)

文章目录 插槽1.插槽 - 默认插槽(组件内可以定制一处结构)2.插槽 - 后备内容&#xff08;默认值&#xff09;3.插槽 - 具名插槽(组件内可以定制多处结构)4.作用域插槽(插槽的一个传参语法) 插槽 插槽分类:默认插槽和具名插槽 1.插槽 - 默认插槽(组件内可以定制一处结构) 作用…...

C# LING查询语法学习,扩展方法的使用

class Program { #region 示例1&#xff1a;不使用LINQ查询数组 //static void Main(string[] args) //{ // int[] nums { 1, 7, 2, 6, 5, 4, 9, 13, 20 }; // List<int> list new List<int>(); // foreach (int item in nums) …...

自然语言推断:微调BERT

微调BERT 自然语言推断任务设计了一个基于注意力的结构。现在&#xff0c;我们通过微调BERT来重新审视这项任务。自然语言推断是一个序列级别的文本对分类问题&#xff0c;而微调BERT只需要一个额外的基于多层感知机的架构&#xff0c;如下图中所示。 本节将下载一个预训练好的…...

立创EDA学习:设计收尾工作

布线整理 ShiftM&#xff0c;关闭铺铜显示 调整结束后再使用快捷键”ShiftM“打开铺铜 过孔 在空白区域加上一些GND过孔&#xff0c;连接顶层与底层的铺铜。放置好”过孔“后&#xff0c;隐藏铺铜&#xff0c;观察刚才放置的过孔有没有妨碍到其他器件 调整铺铜 先打开铺铜区&…...

ShardingSphere之ShardingJDBC客户端分库分表上

目录 什么是ShardingSphere&#xff1f; 客户端分库分表与服务端分库分表 ShardingJDBC客户端分库分表 ShardingProxy服务端分库分表 ShardingSphere实现分库分表的核心概念 ShardingJDBC实战 什么是ShardingSphere&#xff1f; ShardingSphere是一款起源于当当网内部的应…...

rust for循环步长-1,反向逆序遍历

fn main() {for i in (0..3).rev().step_by(1) {print!("{}", i);} } // 打印结果&#xff1a;210Trait std::iter::Iterator fn rev(self) -> Rev< Self > where Self: Sized DoubleEndedIteratorfn step_by(self, step: usize) -> StepBy< Self &…...

编译与运行环境(C语言)

文章目录 前言编译环境编译链接 运行环境 前言 C语言代码的实现&#xff0c;存在两种不同的环境。 第一种是翻译环境&#xff0c;在这个环境中&#xff0c;源代码被转换为可执行的二进制指令。 翻译环境即我们日常使用编译器&#xff0c;将一个 " mission.c " 的文件…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...