牛客网练习赛24 E青蛙

题面：链接：https://www.nowcoder.com/acm/contest/157/E
来源：牛客网
 

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

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

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

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

输入描述:

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

10 <= m,n <= 233

0<a,b<=m

输出描述:

一个数ans表示最小步数

示例1

输入

复制

16 4
2 10
8 15
12 5
13 6

输出

复制

7

说明

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

 

这个题要是用bfs,要想到青蛙有三中方法来走路，第一种是走隧道，第二种是向前跳一格，第三种是往后跳一格。当到了目的地n是返回路径长度就是最短路。还有一点就是每个隧道相当于一步。

代码如下：使用两个队列一个保存路径，一个保存路径长度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const int INF=0x3f3f3f3f;
const double EPS = 1e-10;
inline int read(){
    int ret=0,f=0;char ch=getchar();
    while(ch>'9'||ch<'0') f^=ch=='-',ch=getchar();
    while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return f?-ret:ret;
}
int n,m;
int p[300];
int vis[300];
int dx[]={1,-1};
void bfs(int x){
	queue<int>q;
	q.push(x);
	q.push(0);
	vis[x]=1;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		int val=q.front();
		q.pop();
		if(t==n){
			cout<<val<<endl;
			return ;
		}
		for(int i=0;i<2;i++){
			int x = t+dx[i];
			if(!vis[x]&&x>=0&&x<=n){
				vis[x]=1;
				q.push(x);
				q.push(val+1);
			}
		}
		if(p[t]!=0){
			if(!vis[p[t]]){
				vis[p[t]]=1;
				q.push(p[t]);
				q.push(val+1);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(vis,0,sizeof(vis));
	memset(p,0,sizeof(p));
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		p[a]=b;
	}
	bfs(0);
 	return 0;
}

代码二：使用一个结构题一个保存路径，一个保存长度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pi acos(-1)
using namespace std;
typedef long long ll;
const int maxn=1e7+10;
const int INF=0x3f3f3f3f;
const double EPS = 1e-10;
inline int read(){
    int ret=0,f=0;char ch=getchar();
    while(ch>'9'||ch<'0') f^=ch=='-',ch=getchar();
    while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return f?-ret:ret;
}
struct node{
	int a;
	int val;
	
};
int n,m;
int vis[300];
int dx[2]={1,-1};
int p[300];
void bfs(){
	queue<node>q;
	node m;
	m.a=0;
	m.val=0;
	q.push(m);
	vis[0]=1;
	while(!q.empty()){
		node t = q.front();
		q.pop();
		if(t.a==n){
			cout<<t.val<<endl;
			return ;
		}
		if(p[t.a]){
			node r;
			r.a=p[t.a]; 
			r.val=t.val;
			if(!vis[r.a]){
				vis[r.a]=1;
				r.val+=1;
				q.push(r);	
			}
		}
		for(int i=0;i<2;i++){
			node x;
			x.a=t.a+dx[i];
			x.val=t.val;
			if(x.a>=0&&x.a<=n&&!vis[x.a]){
				vis[x.a]=1;	
				x.val+=1;
				q.push(x);	
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(vis,0,sizeof(vis));
	memset(p,0,sizeof(p));
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		p[a]=b;
	}
	bfs();
 	return 0;
}

搜索学得不好，这几天就好好补补。