hdu 1226 BFS + bfs记录路径

2024-05-28 04:38
文章标签 路径 记录 bfs hdu 1226

本文主要是介绍hdu 1226 BFS + bfs记录路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=1226

为了省空间,可以用vis数组初始化的时候初始化为-1,

发现一个BFS容易错的地方 开始一直WA在这里:就是我int tp=q.front();之后马上q.pop();了,然后才去判断是不是符合条件以break,这样就不能根据q.empty()==1认为没有找到ans 因为这里WA了

其实也可以vis[0] == -1来判断

比较不理解的是 当n==0的时候 %n==0的时候怎么处理

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;const int MAXN = 5000+100;
int n,c,m;
int a[MAXN],vis[MAXN],pre[MAXN];//pre记录路径
int ans[MAXN];queue<int>q;int num;void dfs(int u)
{ans[num++]=vis[u];if(pre[u] == -1)return;dfs(pre[u]);
}void print()
{num--;while(!ans[num])num--;for(int i=num;i>=0;i--)printf("%c",ans[i]+ (ans[i]>9?'A'-10:'0') );putchar('\n');
}void solve()
{CL(vis,0xff);CL(pre,0xff);if(!n && !a[0]){puts("0");return;}if(!n && a[0])//{puts("give me the bomb please");return;}while(!q.empty())q.pop();for(int i=0;i<m;i++)if(a[i]){int tmp=a[i]%n;if(vis[tmp]==-1){vis[tmp]=a[i];//记录tmp由a[i]得来pre[tmp]=-1; //q.push(tmp);}}int tp=0,flag=0;while(!q.empty()){tp=q.front();q.pop();if(!tp){flag=1;break;}for(int i=0;i<m;i++){int tmp=(tp*c+a[i])%n;if(vis[tmp] == -1){vis[tmp]=a[i];pre[tmp]=tp;q.push(tmp);}}}if(!flag){puts("give me the bomb please");return;}num=0;dfs(0);if(num>500){puts("give me the bomb please");return;}print();
}int main()
{//IN("hdu1226.txt");int ncase;scanf("%d",&ncase);while(ncase--){scanf("%d%d%d",&n,&c,&m);char op[5];for(int i=0;i<m;i++){scanf("%s",op);if(op[0] >='A' && op[0] <='F') a[i]=op[0]-'A'+10;else a[i]=op[0]-'0';}sort(a,a+m);solve();}return 0;
}


这篇关于hdu 1226 BFS + bfs记录路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009566

相关文章

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者(Producer)配置1. 创建 Spr

k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)

《k8s上运行的mysql、mariadb数据库的备份记录(支持x86和arm两种架构)》本文记录在K8s上运行的MySQL/MariaDB备份方案,通过工具容器执行mysqldump,结合定时任务实... 目录前言一、获取需要备份的数据库的信息二、备份步骤1.准备工作(X86)1.准备工作(arm)2.手

SpringBoot3应用中集成和使用Spring Retry的实践记录

《SpringBoot3应用中集成和使用SpringRetry的实践记录》SpringRetry为SpringBoot3提供重试机制,支持注解和编程式两种方式,可配置重试策略与监听器,适用于临时性故... 目录1. 简介2. 环境准备3. 使用方式3.1 注解方式 基础使用自定义重试策略失败恢复机制注意事项

Python UV安装、升级、卸载详细步骤记录

《PythonUV安装、升级、卸载详细步骤记录》:本文主要介绍PythonUV安装、升级、卸载的详细步骤,uv是Astral推出的下一代Python包与项目管理器,主打单一可执行文件、极致性能... 目录安装检查升级设置自动补全卸载UV 命令总结 官方文档详见:https://docs.astral.sh/

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

统一返回JsonResult踩坑的记录

《统一返回JsonResult踩坑的记录》:本文主要介绍统一返回JsonResult踩坑的记录,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录统一返回jsonResult踩坑定义了一个统一返回类在使用时,JsonResult没有get/set方法时响应总结统一返回

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

java对接海康摄像头的完整步骤记录

《java对接海康摄像头的完整步骤记录》在Java中调用海康威视摄像头通常需要使用海康威视提供的SDK,下面这篇文章主要给大家介绍了关于java对接海康摄像头的完整步骤,文中通过代码介绍的非常详细,需... 目录一、开发环境准备二、实现Java调用设备接口(一)加载动态链接库(二)结构体、接口重定义1.类型

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键