鏈接：https://www.nowcoder.com/acm/contest/157/E
來源：牛客網

有一只可愛的老青蛙，在路的另一端發現了一個黑的東西，想過去一探究竟。于是便開始踏上了旅途 一直這個小路上有很多的隧道，從隧道的a進入，會從b出來，但是隧道不可以反向走。 這只青蛙因為太老了，所以很懶，現在想請你幫幫慢，問他最少需要幾步才可以到達對面。 將小徑看作一條數軸，青蛙初始在0上，這只青蛙可以向前跳也可以向后跳，但每次只能跳一格，每跳一格記作一步，從隧道進到隧道出算做一步。

輸入描述:
第一行兩個數m,n；表示黑色物品在數軸m點上，數軸上總共有n個隧道接下來n行，每行a，b兩個數，表示從a進會從b出10 <= m,n <= 2330<a,b<=m

輸出描述:

一個數ans表示最小步數
輸入
16 4
2 10
8 15
12 5
13 6
輸出
7

提示： 0-->1-->2-->10-->9-->8-->15-->16 題解：一看題目，我就想用BFS做，但是最后卻卡在了一個細節上，就是在寫check函數的時候，0<a&&a<=n被我寫成0<a<=n，這個真的下次得注意了！ 代碼： #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define mod 1000000007 #define INF 0x3f3f3f3f const int N=250; int n,m; vector<int>s[N]; int ans=INF; int vis[N][N]; int d[N]; struct niu {int x;int step;niu(){}niu(int xt,int st){x=xt,step=st;} }; queue<niu>q; bool check(int a){return 0<a&&a<=n;}//注意這里不能寫成0<a<=n; void bfs() {while(q.size())q.pop();memset(vis,0,sizeof(vis));q.push(niu(0,0));vis[0][0]=1;while(q.size()){niu tmp=q.front();q.pop();if(tmp.x==n){ans=min(ans,tmp.step);return ;}for(int nx: s[tmp.x]){if(check(nx)&&vis[nx][tmp.step]==0){vis[nx][tmp.step]=1;q.push(niu(nx,tmp.step+1));}}int ny=tmp.x+1;if(check(ny)&&vis[ny][tmp.step]==0){vis[ny][tmp.step]=1;q.push(niu(ny,tmp.step+1));}int nz=tmp.x-1;if(check(nz)&&vis[nz][tmp.step]==0){vis[nz][tmp.step]=1;q.push(niu(nz,tmp.step+1));}} }int main(){;ios_base::sync_with_stdio(0); cin.tie(0);cin>>n>>m;int a,b;for(int i=0;i<m;i++){cin>>a>>b;s[a].push_back(b);}/* for(int i=0;i<=n;i++) for(int j: s[i])cout<<j<<endl;*/bfs();cout<<ans<<endl;return 0; }

?

這道題也可以用最短路floyed算法做(這種做法我又犯了一個錯誤，n,m定義全局變量后，又在下面定義成局部變量，這使得調用floyed函數時出錯）

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define mod 1000000007 #define INF 0x3f3f3f3f const int N=250; int n,m; int d[N][N]; void floyed() {for(int k=0;k<=n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]); }int main(){ //這里不能在定義一次n,mios_base::sync_with_stdio(0);cin.tie(0);cin>>n>>m;memset(d,INF,sizeof(d));for(int i=0;i<m;i++){int a,b;cin>>a>>b;d[a][b]=1;}for(int i=1;i<=n;i++){d[i][i-1]=1;d[i-1][i]=1; d[i][i]=0;}floyed();cout<<d[0][n]<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/zhgyki/p/9458856.html

總結

以上是生活随笔為你收集整理的牛客网挑战赛24 青蛙（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。