蓝桥杯DFS自练三题-串变换,玩具蛇,分糖果

 题目一:串变换

 代码解析:

#include <iostream>
using namespace std;
struct Option{
  int select;
  int x;
  int y;
};
string S,T;
int N,K;//N是串的长度,K是操作指令的大小
Option opt[10];//存储所有的指令
bool vis[10];//标记数组,重要;
bool flag;//标记是否找到最终答案

void dfs(string s,int start)//以start为起点开始进行dfs
{
  if(flag)return;//如果找到了最终答案,直接退出
  vis[start]=true;//进行标记
  int x=opt[start].x;
  int y=opt[start].y;
  if(opt[start].select==1)//注意此处要将字符转为数字再转回字符 
    {
        int tmp=(int)(s[x]-'0');
        tmp=(tmp+y)%10;
        s[x]=(char)(tmp+'0');
    }    
    else 
    {
        swap(s[x],s[y]);
    } 
   if(s==T)//S已经变成T,标志位置1并返回 
    {
        flag=1;
        return;
    }
    for(int i=1;i<=K;i++)//开始递归 
    {
        string ss; 
        if(i==start)continue; 
        if(vis[i]==0)//该结点之前未访问 
        {
          ss=s;//将s串复制一份 
          dfs(ss,i);
          vis[i]=false;//退出递归后将第i个结点的标志位置回0 
        }
    }

}
int main()
{
  string temp_S;
    cin>>N;
    cin>>S>>T;
    temp_S=S;//temp_S用于将S串复制一份用于传参 
    cin>>K;
    for(int i=1;i<=K;i++)
    {
        cin>>opt[i].select>>opt[i].x>>opt[i].y;
    } 
     for(int i=1;i<=K;i++)//把每个结点分别作为起点,进行K次dfs 
    {
        vis[10]={0};
        temp_S=S;
        dfs(temp_S,i);
        if(flag)
        {
            cout<<"Yes"<<endl;
            break;
        }
    }
    if(flag==0)cout<<"No"<<endl;
  return 0;
}

题目二:玩具蛇 

#include "iostream"
using namespace std;

int dx[4]={1,0,-1,0};	//方向控制类型 
int dy[4]={0,1,0,-1};
int a[4][4]={0};
int n=0;

void dfs(int stay,int x,int y)	//x,y相当于正在放置的格子的坐标 
{	
	int tx,ty;
	if(stay==16)	//递归终止条件 
	{
        n++;
		return;
	}

	for(int i=0;i<4;i++)	//尝试向四个方向放置 
	{
		tx=x+dx[i];			//方向 
		ty=y+dy[i];
		if(a[tx][ty]==1||tx<0||tx>3||ty<0||ty>3)		//该格子不可放置 或越界 跳过该方向 
		continue;
		a[tx][ty]=1;	// 对已放置的格子进行标记 
		dfs(stay+1,tx,ty);
		a[tx][ty]=0;	//清除标记 
		
	}
}

int main()
{
	void dfs(int stay,int x,int y);

	int stay=0;	//玩具蛇共16节 已放置了stay节 
	int i,k;
	for(i=0;i<4;i++)	//对4x4的格子 枚举玩具蛇第一个步放置的所有可能。 
	{
		for(k=0;k<4;k++)		
		{
			a[i][k]=1;	//对已放置的格子进行标记 
			dfs(1,i,k);
			a[i][k]=0;	//清除标记 
		}
	}
	cout<<n;
	return 0;
}

分糖果 

 

 代码及其解析

#include <iostream>
using namespace std;

int res = 0;
void dfs(int k,int tan1,int tan2)// 第i人选,糖果1,2数量
{
    if(k>=7){ // 枚举完了,看糖果数
        if(!tan1 && !tan2)res++;
          return ;
    }
    for(int i=0;i<=tan1;i++)  // 枚举糖1
        for(int j=0;j<=tan2;j++)    // 枚举糖2
              if(i+j>=2 && i+j<=5) 
                  dfs(k+1,tan1-i,tan2-j);
  return ;
}

int main()
{
  dfs(0,9,16);
  cout<<res;
  return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

4.1-4.5算法刷题笔记(17道题)

4.1-4.5算法刷题笔记 1. 区间和2. 区间合并3. 用队列实现栈&#xff08;queueMain queueTemp;&#xff09;4. 最小栈 1. 单链表模板5. 单链表 2. 双链表模板6. 双链表 3. 模拟栈7. 模拟栈(一个数组即可)8. 表达式求值 4. 队列 tt -1,hh 0;9. 模拟队列 5. 单调栈10. 单调栈 6…

视觉大模型--DAB-deter的深入理解

原理大家参考这篇文章&#xff0c;我主要是根据自己的理解和整个流程图以及代码进行对应&#xff0c;这样更有利于深入理解&#xff1a; 下图是解码器结构图&#xff0c;编码器没动和deter一样的 这张图片基本上说清了模型的结构和传递过程&#xff0c;红色代表切断梯度反向传…

用TensorBoard可视化PyTorch

一、TensorBoard与PyTorch配合使用的基本步骤 PyTorch可以直接与TensorBoard进行集成&#xff0c;因为TensorBoard是一个独立于TensorFlow之外的可视化工具。TensorBoard被设计为支持机器学习实验的可视化&#xff0c;如训练的进度和结果等。PyTorch中的torch.utils.tensorboa…

SSM党员管理系统

一、系统介绍 党员管理系统: 可以方便管理人员对党员管理系统的管理&#xff0c;提高信息管理工作效率及查询效率&#xff0c;有利于更好的为用户提供服务。 主要的模块包括&#xff1a; 1、后台功能&#xff1a; 管理员角色&#xff1a;首页、个人中心&#xff0c;党员管理…

“成像光谱遥感技术中的AI革命:ChatGPT在遥感领域中的应用“

遥感技术主要通过卫星和飞机从远处观察和测量我们的环境&#xff0c;是理解和监测地球物理、化学和生物系统的基石。ChatGPT是由OpenAI开发的最先进的语言模型&#xff0c;在理解和生成人类语言方面表现出了非凡的能力。本文重点介绍ChatGPT在遥感中的应用&#xff0c;人工智能…

Vue-B站学习笔记

1. 路由配置 B站视频之Vue route文件下的index.js app.vue

云原生:5分钟了解一下Kubernetes是什么

在当今的云计算时代&#xff0c;容器化技术变得越来越重要。它能够帮助开发者更高效地部署和管理应用程序。而Kubernetes&#xff0c;作为容器编排领域的领军者&#xff0c;正逐渐成为企业构建和管理云原生应用的核心工具。 近期将持续为大家分享Kubernetes相关知识&#xff…

78、WAF攻防——菜刀冰蝎哥斯拉流量通讯特征绕过检测反制感知

文章目录 菜刀冰蝎哥斯拉 本节主要讲上传了后门&#xff0c;要是用webshell连接工具进行连接&#xff0c;而webshell连接工具特征可能被检测系统识别相关内容。 web防护软件&#xff1a; WEB应用防火墙——WAF入侵检测系统——IDS、HIDS威胁感知——天眼 感知威胁技术&#x…

基于单片机数码管20V电压表仿真设计

**单片机设计介绍&#xff0c;基于单片机数码管20V电压表仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机数码管20V电压表仿真设计的主要目的是通过单片机和数码管显示电路实现一个能够测量0到20V直流电压的电…

如何设计系统容量?

单位每年都会举行运动会&#xff0c;有一个2000m长跑的项目&#xff0c;大约每年报名人员为男选手40人&#xff0c;女选手20人&#xff0c;只有一条橡胶跑道。一次比赛10人齐跑&#xff0c;所以至少需要6场比赛。 2000米的完成时间要求是20分钟&#xff0c;超过20分钟不计数&a…

世强硬创获德佑威授权代理,拓展UV胶粘剂/PUR热熔胶等产品布局

随着下游应用市场产品不断更新迭代&#xff0c;以及企业的环保意识提高&#xff0c;企业对电子胶粘材料的性能要求越来越高&#xff0c;从而推动上游原厂的技术创新与升级&#xff0c;为国内提供更多高性能国产胶粘材料。 基于优良的口碑&#xff0c;世强先进&#xff08;深圳…

关于JVM-三色标记算法剖析

相关系列 深入理解JVM垃圾收集器-CSDN博客 深入理解JVM垃圾收集算法-CSDN博客 深入理解jvm执行引擎-CSDN博客 jvm优化原则-CSDN博客 jvm流程图-CSDN博客 三色标记产生的原因&#xff1f; 在并发标记的过程中&#xff0c;因为标记期间应用线程还在继续跑&#xff0c;对象间的引…

面试题:volatile

一旦一个共享变量&#xff08;类的成员变量、类的静态成员变量&#xff09;被volatile修饰之后&#xff0c;那么就具备了两层语义&#xff1a; 1. 保证线程间的可见性 保证了不同线程对这个变量进行操作时的可见性&#xff0c;即一个线程修改了某个变量的值&#xff0c;这新值…

Javascript进阶内容

1. 作用域 1.1 局部作用域 局部作用域分为函数作用域 和 块级作用域 块级作用域就是用 {} 包起来的&#xff0c;let、const声明的变量就是产生块作用域&#xff0c;var不会&#xff1b;不同代码块之间的变量无法互相访问&#xff0c;里面的变量外部无法访问 1.2 全局作用域…

安卓开机启动流程

目录 一、整体框架二、流程代码分析2.1 Boot ROM2.2 Boot Loader2.3 Kernel层Kernel代码部分 2.4 Init进程Init进程代码部分 2.5 zygote进程zygote代码部分 2.6 SystemServer进程SystemServer代码部分 2.7 启动Launcher与SystemUI 三、SystemServices3.1 引导服务3.2 核心服务3…

Linux|从 STDIN 读取 Awk 输入

简介 在之前关于 Awk 工具的系列文章中&#xff0c;主要探讨了如何从文件中读取数据。但如果你希望从标准输入&#xff08;STDIN&#xff09;中读取数据&#xff0c;又该如何操作呢&#xff1f; 在本文中&#xff0c;将介绍几个示例&#xff0c;展示如何使用 Awk 来过滤其他命令…

开创加密资产新纪元:深度解析ERC-314协议

随着加密资产市场的不断发展和区块链技术的日益成熟&#xff0c;新的协议和标准不断涌现&#xff0c;其中包括了ERC-314协议。本文将深入分析ERC-314协议的特点、功能以及对加密资产市场可能产生的影响。 1. ERC-314协议简介 ERC-314协议是一项建立在以太坊区块链上的新提案&a…

软件测试中的43个功能测试点总结

功能测试就是对产品的各功能进行验证&#xff0c;根据功能测试用例&#xff0c;逐项测试&#xff0c;检查产品是否达到用户要求的功能。针对web系统的常用测试方法如下&#xff1a; 1、页面链接检查&#xff1a; 每一个链接是否都有对应的页面&#xff0c;并且页面之间切换正…

设计模式之状态模式讲解

概念&#xff1a;又称为状态对象模式&#xff0c;该模式允许一个对象在其内部状态改变时改变其行为。状态模式的核心是封装&#xff0c;状态的变更引起行为的变动&#xff0c;从外部看来就好像该对象对应的类发生改变一样。 抽象状态&#xff1a;用以封装环境对象的一个特定状态…

thinkphp6使用阿里云SDK发送短信

使用composer安装sdk "alibabacloud/dysmsapi-20170525": "2.0.24"封装发送短信类 发送到的短信参数写在env文件里面的 #发送短信配置 [AliyunSms] AccessKeyId "" AccessKeySecret "" signName"" templateCode"&…