第一道同时用BFS和DFS两种方法做出来的题目
最大的注意点就是判断是否经历过该楼层
#include<bits/stdc++.h> using namespace std; int n,a,b; int dis[201],f[201]; queue<int> q; bool check(int x){ return x>=1&&x<=n; } void bfs() { int t; while(!q.empty()){ int p=q.front(); q.pop(); if(p==b){ cout<<dis[b]; return; } t=p+f[p]; if(check(t)&&dis[t]==0){//注意进行判断是否已经经历过这个楼层 dis[t]=dis[p]+1; q.push(t); } t=p-f[p]; if(check(t)&&dis[t]==0){ dis[t]=dis[p]+1; q.push(t); } } cout<<-1; } int main() { cin>>n>>a>>b; for (int i = 1; i <= n; i++){ cin>>f[i]; } q.push(a); dis[a]=0; bfs(); return 0; }
这道题用DFS好难,做了好久
#include<bits/stdc++.h> using namespace std; int n,a,b,ans=INT_MAX;//注意我们求得是最小值,也就是说我们需要遍历所有可能 int to[201]; bool vis[201]; bool check(int x,int sum) { return !vis[x]&&x>=1&&x<=n&&sum<ans; } void dfs(int now,int sum) { if(now==b){ ans=min(sum,ans); return; } vis[now]=1;//遍历过赋值为1 int t=now+to[now]; if(check(t,sum)){ dfs(t,sum+1); } t=now-to[now]; if(check(t,sum)){ dfs(t,sum+1); } vis[now]=0;//回溯,当该序列中由于下面的序列符合条件,一定要记得将其置为未遍历状态 } int main() { cin>>n>>a>>b; for(int i=1;i<=n;i++){ cin>>to[i]; } vis[a]=1; dfs(a,0); if(ans!=INT_MAX){ cout<<ans; } else{ cout<<-1; } return 0; }
原文:https://www.cnblogs.com/lvjt0208/p/14628894.html