浙江工业大学迎新预赛(容器的使用)

浙江工业大学迎新预赛

https://www.nowcoder.com/acm/contest/52#question

F题

首先关于常规的 dfs 与 bfs :

不同:dfs 是对栈的使用,通过递归进行。bfs 是对队列的使用,可通过C++ 中的queue进行。二者都需要不断对执行变量进行更新,一个通过递归,一个通过放入队列

也有相同点:二者对执行变量的更新一般是利用for循环(如果是只有两个选择,则就不需要使用循环,直接连用即可)

上面为 dfs 与  bfs 的常规用法,即变量更新是由不变的规则进行的,通过循环即可

而F题的青蛙妈妈的跳跃方向不能是一成不变的,而是有不可控制的规则限定的,这时利用vector容器将其能够相互移动的单位装起来,提供给queue 从而实现bfs的变量更新

先把可互相移动的位置用容器 vector 存起来

然后把存在容器 vector 内的东西放到 queue 中 进行 bfs 操作(同时要把移动过的位置标记起来,防止来回移动)

废话这么多,实际就是想说,凡是遇到移动没有规则(即不能依靠循环更新移动)的问题时,vector 与 queue 的连用将使 bfs 能轻松应对

原文地址:https://www.cnblogs.com/MekakuCityActor/p/8158834.html