洛谷 P1032 字串变换 广搜[通俗易懂]

洛谷 P1032 字串变换 广搜

大家好,又见面了,我是全栈君。

这道题原本我用深搜,结果会T,wcnm,然后就直接参考题解了

 

 1 Const maxn=10000;  2 maxq=100000;  3 Var a:array[0..1,0..maxn]of string;//变换规则   4 q:array[0..1,0..maxq]of string;//两个队列   5 step:array[0..1,0..maxn]of longint;//步数  6 head,tail:array[0..1]of longint;//两个队列的头指针和尾指针   7 int,aim,s1,s2,s:string;  8  n:longint;  9 Procedure split(s:string);//将目标状态和初始状态记录下来  10 var k:longint; 11 begin 12 k:=pos(' ',s); 13 s1:=copy(s,1,k-1); 14 s2:=copy(s,k+1,length(s)-k); 15 end; 16 Procedure init; //读入 17 begin 18  readln(s); 19  split(s); 20 int:=s1;//初始状态 21 aim:=s2;//目标状态  22 n:=0; 23 while not eof do 24  begin 25  readln(s); 26 if s='' then exit; 27  inc(n); 28  split(s); 29 a[0,n]:=s1;//初始的可以转换的状态 30 a[1,n]:=s2;//由初始状态转换一步得到的目标状态 31  end; 32 end; 33 Function vis(s:string;t:byte):boolean; 34 var i:longint; 35 begin 36 vis:=false; 37 for i:=1 to tail[t] do//遍历队列 38 if q[t,i]=s then exit(true);//如果找到目标状态就返回值true  39 end; 40 Procedure print(k:longint); 41 begin 42 writeln(k);//(如果合法)输出最少变换步数  43  halt; 44 end; 45 Procedure check(t:byte); 46 var i:longint; 47 begin 48 for i:=1 to tail[1-t] do //遍历队列(当前的状态保存在队列里) 49 if q[1-t,i]=q[t,tail[t]] then //如果两个广搜碰头了 50 print(step[1-t,i]+step[t,tail[t]]);//总的步数就是两个广搜步数之和  51 end; 52 Procedure bfs(t:byte); //广搜(t=0是正着搜,t=1是反着搜) 53 var i,j,k:longint; 54 pre,tmp:string; 55 begin 56 inc(head[t]);//头指针加一 57 pre:=q[t,head[t]];//入队  58 for i:=1 to n do//遍历变换规则  59  begin 60 k:=length(a[t,i]); 61 for j:=1 to length(pre)-k+1 do//按照变换规则扩展状态  62  begin 63 if copy(pre,j,k)=a[t,i] then//如果规则符合  64  begin 65 tmp:=copy(pre,1,j-1)+a[1-t,i]+copy(pre,j+k,length(pre)-j-k+1);//扩展下一个状态  66 if not vis(tmp,t) then//如果没有找到目标状态  67  begin 68  inc(tail[t]); 69 q[t,tail[t]]:=tmp; 70 step[t,tail[t]]:=step[t,head[t]]+1;//步数++  71  end; 72 check(t);//检查是否终止搜索(注意位置,不然就T了) 73  end; 74  end; 75  end; 76 end; 77 Procedure doublebfs;//用数组下标来区分两个队列和两个广搜  78 begin 79 head[0]:=0;//第一个队列的头指针 80 head[1]:=0;//第二个队列的头指针 81 tail[0]:=1;//第一个队列的尾指针 82 tail[1]:=1;//第二个队列的尾指针  83 q[0,1]:=int;//初始状态 84 q[1,1]:=aim;//目标状态 85 step[0,1]:=0;//步数 86 step[1,1]:=0;//步数  87 while (head[0]<tail[0])and(head[1]<tail[1])do 88 if tail[1]<tail[0] then 89 bfs(1) else bfs(0);//保持两个广搜的同步  90 end; 91 Begin 92  init; 93  doublebfs; 94 writeln('NO ANSWER!'); 95 End.

 

转载于:https://www.cnblogs.com/third2333/p/6829212.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/108511.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java rpc接口_java调用python模型

    java rpc接口_java调用python模型依赖<!–XMRPC相关依赖–><dependency><groupId>org.apache.xmlrpc</groupId><artifactId>xmlrpc-server</artifactId><version>3.1.3</version></dependency>

    2022年10月12日
  • war如何解压[通俗易懂]

    war如何解压[通俗易懂]工具/原料 WinRAR eclipse tomcat9.0 用解压软件解压 如果只是想看war包中的内容,可以直接用解压软件解压war包就可以了。 如图我是用WinRAR解压的。右键war包选择打开方式,接着选择一个解压软件,最后将文件夹解压到电脑上就可以了,我是解压到桌面上。 解压后就可以看到桌面上多了一个文件夹。打开文件夹,就能看到war包里面的内容了。 END 用eclipse解压 如果是想编辑该w

  • Java开发中的Memcache原理及实现

    Java开发中的Memcache原理及实现

  • CentOS8快速部署轻量级自动化运维平台Spug

    CentOS8快速部署轻量级自动化运维平台SpugSpug面向中小型企业设计的轻量级无Agent的自动化运维平台,整合了主机管理、主机批量执行、主机在线终端、文件在线上传下载、应用发布部署、在线任务计划、配置中心、监控、报警等一系列功能。Spug的特性批量执行:主机命令在线批量执行在线终端:主机支持浏览器在线终端登录文件管理:主机文件在线上传下载任务计划:灵活的在线任务计划发布部署:支持自定义发布部署流程配置中心:支持KV、文本、json等格式的配置监控中心:支持站点、端口、进程、自定义等监控报警中心:支持短信、

  • python抢淘宝的东西-Python 实现毫秒级淘宝抢购脚本的示例代码

    python抢淘宝的东西-Python 实现毫秒级淘宝抢购脚本的示例代码本篇文章主要介绍了Python通过selenium实现毫秒级自动抢购的示例代码,通过扫码登录即可自动完成一系列操作,抢购时间精确至毫秒,可抢加购物车等待时间结算的,也可以抢聚划算的商品。博主不提供任何服务器端程序,也不提供任何收费抢购软件。该文章仅作为学习selenium框架的一个示例代码。该思路可运用到其他任何网站,京东,天猫,淘宝均可使用,且不属于外挂或者软件之类,只属于一个自动化点击工具,…

  • Python 万能代码模版:爬虫代码篇「建议收藏」

    Python 万能代码模版:爬虫代码篇「建议收藏」你好,我是悦创。很多同学一听到Python或编程语言,可能条件反射就会觉得“很难”。但今天的Python课程是个例外,因为今天讲的**Python技能,不需要你懂计算机原理,也不需要你理解复杂的编程模式。**即使是非开发人员,只要替换链接、文件,就可以轻松完成。并且这些几个实用技巧,简直是Python日常帮手的最佳实践。比如:爬取文档,爬表格,爬学习资料;玩转图表,生成数据可视化;批量命名文件,实现自动化办公;批量搞图,加水印、调尺寸。接下来,我们就逐一用Python实

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号