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