A hdu1548
/*此题较为简单,只有两个方向典型的bfs将所有情况记录下来,满足宽度优先原则*/
/*此题只有两个方向,那么抽象为二叉树,又因为所找的目标节点已知且要求的最短路所以果断bfs。*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int n, a, b;//共有n层楼,从a层到 b层,a,b是随机给的
int step[205];
int vis[205];
int tall, cnt;//tall为一个临时变量保存当前高度当前将要向上或者下走,cnt为当前为第几级
int times[205];//宽度优先搜索将所走的路的长度都记录下来
int bfs(){
queue<int>q;
q.push(a);
vis[a] = 1;
times[a] = 0;
while(!q.empty()){
cnt = q.front();
q.pop();
for(int i = 0; i < 2; i++){//两方向一个向上走一个向下走
if( i == 0)
tall = cnt + step[cnt];//向上走
else
tall = cnt- step[cnt];//向下走,判断完向上走后得回来回到向上走之前的那个点向下走
if(tall < 1 || tall > n) continue ;//当前的台阶书不能大于n,或不能小于1
if(!vis[tall]){
q.push(tall);
vis[tall] = 1;/*你可能会疑惑为什么标记,因为按照宽度搜索每一步都是最近的(短的),且每个点搜索一次,它有别于dfs的就在这里,dfs是从一个根,或节点走到树叶找到目标或者没找到但是到了边界在回溯,bfs是由 根 到树叶一层扫完,深度加一再扫下一层并记录下来,所以所有点只扫一次,因此bfs利于算最短路,而dfs利于判断是否可达目标地点。*/
times[tall] = times[cnt] + 1;/*这里用数组times原因是保存每个点的权值也就是次数,bfs会将每个情况都记录,这里用数组记录每到新的一层都加一 */
}
if(tall == b) return times[tall];
}
}
return -1;
}
int main()
{
while(scanf("%d", &n) != EOF && n){
memset(step, 0, sizeof(step));
memset(vis, 0, sizeof(vis));
scanf("%d%d", &a, &b);
for(int i = 1; i <= n; i++) scanf("%d", &step[i]);
printf("%d\n", bfs());
}
return 0;
}
-------------------------------------------------------------------------------
B poj2488
/*这题可以简单的理解为dfs打印路径(路径要求按照字典序打印ABC...),搜索很简单重点是搜索的方向是个固定值。下面有个简单例图*/
A B C