青蛙

[编程题]青蛙

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有一只可爱的老青蛙，在路的另一端发现了一个黑的东西，想过去一探究竟。于是便开始踏上了旅途

一直这个小路上有很多的隧道，从隧道的a进入，会从b出来，但是隧道不可以反向走。

这只青蛙因为太老了，所以很懒，现在想请你帮帮慢，问他最少需要几步才可以到达对面。

将小径看作一条数轴，青蛙初始在0上，这只青蛙可以向前跳也可以向后跳，但每次只能跳一格，每跳一格记作一步，从隧道进到隧道出算做一步。

输入描述:

第一行两个数m,n；表示黑色物品在数轴m点上，数轴上总共有n个隧道
接下来n行，每行a，b两个数，表示从a进会从b出

10 <= m,n <= 233

0<a,b<=m

输出描述:

一个数ans表示最小步数

示例1

输入

输出

说明

0-->1-->2-->10-->9-->8-->15-->16

算法知识视频讲解

Lurker3333

发表于 2020-04-17 23:27:46

这道题其实是我练习dp的时候看到的，这道题应该归在dp里吗？？（可能是我太菜了dp不会做吧。。。）我直接用dfs做了，还是比较容易的一道dfs题目。思路：dfs每一步的坐标，三种情况：1.向前一步 2.向后一步 3.如果有隧道，进入隧道。附上代码应该还是很好懂的。 #include<bi 展开全文

我wyn实名上网

发表于 2024-07-20 11:54:53

搜索dp，背包，点击这道题，然后图论解决...... 题目可以抽象成每一个点 i,i+1之间都有度数为1的边连接，在此基础上还额外给出了其它度数为1的边套dijkstra模板即可 using namespace std; const int N = 1e3 + 10; const int inf 展开全文