DFS代码

#include<iostream>
#include<cstdio>
using namespace std;
#define Min(a,b) (a<b)?a:b
const int MAX_N=;
const int INF=0x30303030;
int floors[MAX_N];
int N, A, B;
int step[MAX_N];
int dfs(int k)
{
if(k<||k>N) return INF;
if(step[k]!=-)
{
return step[k];
}
if(k==B)
{
return ;
}
return step[k]=Min(dfs(k-floors[k])+,dfs(k+floors[k])+);
} int main()
{
while(scanf("%d",&N)!=EOF&&N!=)
{
scanf("%d %d",&A, &B);
for(int i=; i<=N; i++)
{
scanf("%d",&floors[i]);
}
memset(step,-,sizeof(step));
int ans=dfs(A);
if(ans>=INF)
{
printf("-1\n");
}
else
{
printf("%d\n",ans);
}
} return ;
}

BFS:AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_N=;
const int INF=0x30303030;
int floors[MAX_N];
int N, A, B;
typedef pair<int, int> P;
int vis[MAX_N]; int bfs()
{
memset(vis, , sizeof(vis));
queue<P> que;
que.push(P(,A));
vis[A]=;
while(!que.empty())
{
P pos=que.front();que.pop();
int k=pos.second;
int step=pos.first;
if(k==B)
{
return step;
}
for(int i=-; i<=; i++)
{
int next=(k + i*floors[k]);
if(next>=&&next<=N&&!vis[next])
{
vis[next]=;
que.push(P(step+,next));
}
} } return INF;
} int main()
{
while(scanf("%d",&N)!=EOF&&N!=)
{
scanf("%d %d",&A, &B);
for(int i=; i<=N; i++)
{
scanf("%d",&floors[i]);
}
int ans=bfs();
if(ans==INF)
{
printf("-1\n");
}
else
{
printf("%d\n",ans);
}
} return ;
}

最新文章

  1. iOS开发中多线程间关于锁的使用
  2. javascript的propertyIsEnumerable()方法使用介绍
  3. Eclipse连接到My sql数据库之前操作
  4. 【fedora】强制解除yum锁定
  5. exec方法
  6. Linux下利用ioctl函数获取网卡信息
  7. BOM 之 screen history
  8. NHibernate的常见问题及解决方案
  9. DCalendar增加月份选择功能--简单jQuery日期选择器插件改动
  10. ios -Unity3D的EasyAR集成到已经有项目中。
  11. Maven Install报错:Perhaps you are running on a JRE rather than a JDK?
  12. [Android] Android 去掉界面标题栏的方法
  13. caffe中的lr_policy
  14. java.io.Serializable 序列化问题【原】
  15. 使用git命令行解决冲突
  16. Pyhton基础知识(一)
  17. Axure学习(一)
  18. Codeforces Round #258 (Div. 2) E. Devu and Flowers 容斥
  19. centos端口管理
  20. Lambda表达式中使用正则表达式

热门文章

  1. L2 范数 L1 范数 出租车范数
  2. android ui篇 自己写界面
  3. Android UI Design
  4. Shell传参的多种方式
  5. (转载)C #开源框架
  6. C#快速入门笔记(1)——基础语法
  7. Data Structure Array: Find the two numbers with odd occurrences in an unsorted array
  8. IE浏览器和CSS盒模型【转】
  9. CSS3响应式侧边菜单
  10. 手机端适配rem代码片段