洛谷 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)


相关推荐

  • idea2019永久激活注册码3月最新在线激活

    idea2019永久激活注册码3月最新在线激活,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 122. 买卖股票的最佳时(状态机模型)[通俗易懂]

    122. 买卖股票的最佳时(状态机模型)[通俗易懂]原题链接给定一个数组 prices ,其中 prices[i] 是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。示例 1:输入: prices = [7,1,5,3,6,4]输出: 7解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4

  • handlersocket mysql,MySQL插件HandlerSocket

    handlersocket mysql,MySQL插件HandlerSocketHandlerSocket是MySQL的一个插件,用来实现NoSQL功能,用于跳过MySQL的SQL层面,直接访问内部的InnoDB存储引擎。wgethttp://dev.mysql.com/get/Downloads/MySQL-5.5/MySQL-client-5.5.11-1.rhel4.i386.rpmwgethttp://dev.mysql.com/get/Downloads/…

  • 阿里图床api_阿里远程图床

    阿里图床api_阿里远程图床介绍:一款非常美观且极简响应式的阿里图床PHP源码服务器要求支持php修复了浏览器复制出错的bug网盘下载地址:http://kekewl.cc/3NvM8RdOWui0图片:

  • 方差及常见分布的方差计算与推导公式_超几何分布的期望和方差

    方差及常见分布的方差计算与推导公式_超几何分布的期望和方差1.介绍方差定义和性质2.离散型随机变量(01分布,二项分布,泊松分布,几何分布,超几何分布)和连续型随机变量(均匀分布,指数分布,正态分布)分布的方差计算以及推导过程,并汇总形成表格,方便查阅和记录

  • c++事件循环(win32消息机制)

    1.windows消息循环if(GetMessage(&msg,NULL,0,0)){TranslateMessage(&msg);//消息转化DispatchMessage(&msg);//消息派遣.把TranslateMessage转换的消息发送到窗口的消息处理函数,此函数在窗口注册时已经指定}执行过程:消息循环调用G…

发表回复

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

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