蓝桥真题--路径之谜DFS解法

路径之谜

思路

在这里插入图片描述

  • 前置知识:深度搜索模板
  • 搜索所有可以找的路径,将走过的靶子减去一
  • 走到最后一个格子的时候,直接去判断所有的靶子
  • 只有除最后一个位置的靶子,其余靶子都归零的时候,判断一个最后一个位置横坐标和纵坐标的靶子
  • 如果这两个靶子都是1,是我们要的答案,输出路径
  • 每次走过一个格子,都将对应的坐标存入一个path数组中,回溯时就将他复原回去
  • 对于其他状态也需要进行复原,美名其曰-恢复现场

Coding

#include <iostream>
#include <vector>
using namespace std;
const int N = 21;
int vx[] = {0,0,1,-1};
int vy[] = {1,-1,0,0};
int xba[N];
int yba[N];
int path[N*N];
int n, idx;
bool st[N][N];

inline void dfs(int x, int y) {
	if (x == n-1 && y == n-1) {
		for (int i = 0; i < n-1; i++) {
			if (xba[i] || yba[i]) return;
		}
		if (xba[n-1] == 1 && yba[n-1] == 1) {
			path[idx ++] = n*y+x;
			for (int j = 0; j < idx; j++) {
				cout << path[j] << ' ';
			}cout << endl;
		}
	}
	for (int i = 0; i < 4; i++) {
		int nx, ny;
		nx = x + vx[i], ny = y + vy[i];
		if (x >= 0 && y >= 0 && x < n && y < n && !st[x][y]) {
			st[x][y] = true;
			xba[x]--;
			yba[y]--;
			path[idx ++] = n*y+x;
			dfs(nx, ny);
			xba[x]++;
			yba[y]++;
			idx--;
			st[x][y] = false;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> xba[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> yba[i];
	}
	dfs(0, 0);
}

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

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

相关文章

Stale Diffusion、Drag Your Noise、PhysReaction、CityGaussian

本文首发于公众号&#xff1a;机器感知 Stale Diffusion、Drag Your Noise、PhysReaction、CityGaussian Drag Your Noise: Interactive Point-based Editing via Diffusion Semantic Propagation Point-based interactive editing serves as an essential tool to compleme…

爬虫 新闻网站 以湖南法治报为例(含详细注释) V1.0

目标网站&#xff1a;湖南法治报 爬取目的&#xff1a;为了获取某一地区更全面的在湖南法治报已发布的宣传新闻稿&#xff0c;同时也让自己的工作更便捷 环境&#xff1a;Pycharm2021&#xff0c;Python3.10&#xff0c; 安装的包&#xff1a;requests&#xff0c;csv&#xff…

RabbitMQ3.13.x之七_RabbitMQ消息队列模型

RabbitMQ3.13.x之七_RabbitMQ消息队列模型 文章目录 RabbitMQ3.13.x之七_RabbitMQ消息队列模型1. RabbitMQ消息队列模型1. 简单队列2. Work Queues(工作队列)3. Publish/Subscribe(发布/订阅)4. Routing(路由)5. Topics(主题)6. RPC(远程过程调用)7. Publisher Confirms(发布者…

2024-04-26 学习笔记(工业大模型,SAM优化)

坚持每周一篇&#xff0c;加油。 1.穷人的思想钢印&#xff1a;踏实做事情&#xff0c;不做马屁精 摘要&#xff1a;大模型摘要和文章意思相反。。可知这个思想钢印也传递给了AI Raiden说&#xff1a;最近一直在想一句话&#xff1a;假如你混了很久还是一事无成&#xff0c;不…

JavaWeb前端基础(HTML CSS JavaScript)

本文用于检验学习效果&#xff0c;忘记知识就去文末的链接复习 1. HTML 1.1 HTML基础 结构 头<head>身体<body> 内容 图片<img>段落<p>图标<link> 标签 单标签双标签 常用标签 div&#xff1a;分割块span&#xff1a;只占需要的大小p&…

「 典型安全漏洞系列 」12.OAuth 2.0身份验证漏洞

在浏览网页时&#xff0c;你肯定会遇到允许你使用社交媒体帐户登录的网站。此功能一般是使用流行的OAuth 2.0框架构建的。本文主要介绍如何识别和利用OAuth 2.0身份验证机制中发现的一些关键漏洞。 1. OAuth产生背景 为了更好的理解OAuth&#xff0c;我们假设有如下场景&#…

全国日照时数空间分布数据/月度降雨量分布/月均气温分布

引言 地理遥感生态网结合1971-2021年各地区地面气象监测站数据&#xff0c;应用气候数据空间插值软件Anusplin预测全国日照时数分布数据成果。得出全国各个省市自治区日照时数分布图&#xff0c;全国各省市自治区日照时数数据产品是地理遥感生态网推出的气象气候类数据产品之一…

自定义实现shell/bash

文章目录 函数和进程之间的相似性shell打印提示符&#xff0c;以及获取用户输入分割用户的输入判断是否是内建命令执行相关的命令 全部代码 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#…

人工智能研究生前置知识—jupyter notebook快速上手使用

jupyter notebook快速上手使用 前置说明 使用的前置要求安装了anaconda的环境 特点&#xff1a;以代码块和单元块为基础&#xff0c;可以嵌入Markdown格式的说明文字 通知可以嵌入魔法函数&#xff0c;并导出为指定的格式 格式.ipynb&#xff09;&#xff08;不仅仅可以运行py…

支持多元AI场景应用,宁畅“NEX AI Lab”开放试用预约中

3月29日&#xff0c;宁畅在京举行发布会&#xff0c;正式发布“全局智算”战略&#xff0c;并在会上推出战略性新品“AI算力栈”&#xff0c;旨在有效解决大模型产业落地的全周期问题。 据宁畅CTO赵雷介绍&#xff0c;“AI算力栈”集成了宁畅在AI计算领域的软硬件能力&#xff…

FJSP:蜣螂优化算法( Dung beetle optimizer, DBO)求解柔性作业车间调度问题(FJSP),提供MATLAB代码

一、柔性作业车间调度问题 柔性作业车间调度问题&#xff08;Flexible Job Shop Scheduling Problem&#xff0c;FJSP&#xff09;&#xff0c;是一种经典的组合优化问题。在FJSP问题中&#xff0c;有多个作业需要在多个机器上进行加工&#xff0c;每个作业由一系列工序组成&a…

实现点击用户头像或者id与其用户进行聊天(vue+springboot+WebSocket)

用户点击id直接与另一位用户聊天 前端如此&#xff1a; <template><!-- 消息盒子 --><div class"content-box" :style"contentWidth"><!-- 头像&#xff0c;用户名 --><div class"content-box-top box--flex">&l…

大数据毕业设计Python+Spark知识图谱高考志愿推荐系统 高考数据分析 高考可视化 高考大数据 计算机毕业设计 机器学习 深度学习 人工智能

附件3 文山学院本科生毕业论文&#xff08;设计&#xff09;开题报告 姓名 性别 学号 学院 专业 年级 论文题目 基于协同过滤算法的高考志愿推荐系统的设计与实现 □教师推荐题目 □自拟题目 题目来源 题目类别 指导教师 选题的目的、意义(理论…

C++从入门到精通——初步认识面向对象及类的引入

初步认识面向对象及类的引入 前言一、面向过程和面向对象初步认识C语言C 二、类的引入C的类名代表什么示例 C与C语言的struct的比较成员函数访问权限继承默认构造函数默认成员初始化结构体大小 总结 前言 面向过程注重任务的流程和控制&#xff0c;适合简单任务和流程固定的场…

spring boot学习第十六篇:配置多数据源

1、代码参考&#xff1a; dynamic-ds/spring-boot-dynamic-ds at main veminhe/dynamic-ds GitHub 2、验证 2.1调用POST接口http://localhost:8081/hmblogs/blog/addBlog 2.2改动数据源为BJ 然后调用接口添加数据 然后查看ds0库的博客数据

Open CASCADE学习|放样建模

在CAD软件中&#xff0c;Loft&#xff08;放样&#xff09;功能则是用于创建三维实体或曲面的重要工具。通过选取两个或多个横截面&#xff0c;并沿这些横截面进行放样&#xff0c;可以生成复杂的三维模型。在CAD放样功能的操作中&#xff0c;用户可以选择不同的选项来定制放样…

Redis实战篇-集群环境下的并发问题

实战篇Redis 3.7 集群环境下的并发问题 通过加锁可以解决在单机情况下的一人一单安全问题&#xff0c;但是在集群模式下就不行了。 1、我们将服务启动两份&#xff0c;端口分别为8081和8082&#xff1a; 2、然后修改nginx的conf目录下的nginx.conf文件&#xff0c;配置反向代…

matrix-breakout-2-morpheus 靶机渗透

信息收集&#xff1a; 1.nmap存活探测&#xff1a; nmap -sn -r 192.168.10.1/24 Starting Nmap 7.94SVN ( https://nmap.org ) at 2024-04-06 12:13 CST Nmap scan report for 192.168.10.1 Host is up (0.00056s latency). MAC Address: 00:50:56:C0:00:08 (VMware) Nmap…

深入go泛型特性之comparable「附案例」

写作背景 如果你经常遇到一些操作&#xff0c;比如将 map 转换为 slice&#xff0c;判断一个字符串是否出现在 map 中&#xff0c;slice 中是否有重复元素等等&#xff0c;那你对下面这个库肯定不陌生。 github.com/samber/lo最近抽业余时间在看了源码&#xff0c;底层用了范…

c语言实现2048小游戏

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <conio.h>int best 0 ;// 定义2048游戏的结构体 typedef struct { int martix[16]; // 当前4*4矩阵的数字 int martixPrior[16]; // 上一步的4*4矩阵的数字 int emptyIndex[16…