/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2012 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1548
Name : 1548 A strange lift
Date : Sunday,April 1, 2012
Time Stage : many hours
Result:
5685230 2012-04-01 18:17:43 Accepted 1548
0MS 244K 1689 B
C++ pyy
Test Data :
Review :
一开始一直MLE,真是莫名奇妙啊,完全不知道原因,在原代码的基础上改来改去不得其法。
后来直接重新写一遍,酸酸地AC了……
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
#define INF (0x3f3f3f3f)
#define MAXN (202)
#define MAXM (100)
#define DB /##/
#define LL __int64
#define _IN(a) (0 < (a) && (a) <= n)
#define CHECK(a) (_IN(a) && -1 == step[(a)])
#define LOAD(a) do { q.push(a); step[(a)] = step[t] + 1; } while(0)
int n, a, b;
int step[MAXN], next[MAXN];
void bfs()
{
int t, na, nb;
queue<int> q;
q.push(a);
while (!q.empty())
{
t = q.front();
q.pop();
if (t == b)
break;
na = t + next[t];
nb = t - next[t];
if (CHECK(na))
{
LOAD(na);
/*
q.push(na);
step[na] = step[t] + 1;
*/
}
if (CHECK(nb))
{
LOAD(nb);
/*
q.push(nb);
step[nb] = step[t] + 1;
*/
}
}
}
int main()
{
int i;
while (scanf("%d", &n), n)
{
scanf("%d %d", &a, &b);
MEM(step, -1);
step[a] = 0;
for (i = 1; i <= n; ++i)
scanf("%d", &next[i]);
bfs();
printf ("%d\n", step[b]);
}
return 0;
}
分享到:
相关推荐
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
详细地介绍BFS的思路模式以及用几个案例教授怎么运用BFS去解题。
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
算法之BFS与DFS
广度优先搜索算法—BFS的相关代码,包括循环队列的代码
搜索入门之BFS深度优先搜索.ppt 搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。 搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合...
宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于...
本C++代码解决了八数码问题,采用深度优先,广度优先和A*算法实现,基于visual studio 2017
基于python的广度优先搜索算法BFS设计与实现
void BFS(list<int> *the_a,int the_N,int the_S,int *the_b){ int *m=new int[the_N]; for(int k1=0;k1;k1++) m[k1]=0; m[the_S-1]=1; queue<int> qu; qu.push(the_S-1); while(!qu.empty()){ list<int>::...
2分图匹配的BFS实现,C/C++源码。适用于稀疏二分图,边较少,增广路较短。
能够提取最短路径 和最长路径 的 广度优先搜索 BFS (Breadth-first search)代码, 编写语言C++
This is a demo visualizing the execution of various path...不同算法的路径搜寻执行过程可视化程序。 包含5个算法 A* (曼哈顿距离) A* (欧式距离) A* (切比雪夫距离) Dijkstra Bi-Directional Breadth-First-Search
这是ACM中也比较重要的一个知识点,其中的资源包含文档和PPT,当中有搜索的概述,有bfs和dfs,有需要的可以看看!
从最基础的迷宫问题看深搜和宽搜的内涵,理解最基础的穷举搜索。
ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文字符串 ACM比赛常见算法之BFS算法+back回文...
MATLAB源码集锦-基于BFS广度优先搜索算法代码
个人新项目可作毕设基于python实现的广度优先遍历搜索(BFS)源码含实验结果及总结操作说明.zip个人新项目可作毕设基于python实现的广度优先遍历搜索(BFS)源码含实验结果及总结操作说明.zip个人新项目可作毕设基于...