(1)从起始点出发,将该点可以达到的每个点进行入队,同时将他们的时间设置为起始点加1 ;
(2)只要队不为空,对每个出队的点都进行相似起始点的操做;
(3)直到出现某一个出队元素的点的坐标大于原始距离。
注意:要对已通过的点进行标记,防止重复访问。web
问题描述:游戏机由 N 个特殊弹簧排成一排,编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处,经过按动弹簧,能够选择把小球向右弹射 jump[i] 的距离,或者向左弹射到任意左侧弹簧的位置。也就是说,在编号为 i 弹簧处按动弹簧,小球能够弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧(若 i+jump[i]>=N ,则表示小球弹出了机器)。小球位于编号 0 处的弹簧时不能再向左弹。为了得到奖励,你须要将小球弹出机器。请求出最少须要按动多少次弹簧?算法
实现代码数据结构
#define MaxSize 100 //定义存储的点的数据结构 typedef struct{ int loc; //位置 int time; //时间 }Gu; int mark[MaxSize]={0}; //标记防止重复访问 Gu Queue[20]; //队列 int rear,front=-1;
//出队和入队操做 void EnQueue(int loc,int time){ Gu t; mark[loc]=1; t.loc=loc; t.time=time; rear++; Queue[rear]=t; } Gu DeQueue(){ front++; return Queue[front]; }
//接收输入数据 int Input(int jump[]){ int n,i; printf("最小跳跃数\n"); printf("请输入弹簧个数:"); scanf("%d",&n); printf("请输入弹簧弹动的距离:"); for(i=0;i<n;i++) scanf("%d",&jump[i]); return n; }
//广度优先搜索 int CountMin(int jump[],int n){ Gu t; int i; EnQueue(0,0); while(rear!=front) //栈不为空则继续 { t=DeQueue(); if(t.loc>=n) return t.time; else { for(i=0;i<t.loc;i++) if(mark[i]==0) EnQueue(i,t.time+1); EnQueue(t.loc+jump[t.loc],t.time+1); } } }
void Output(int n){ printf("最小的步数为:%d",n); }
int main(){ int jump[MaxSize],n,res; n=Input(jump); res=CountMin(jump,n); Output(res); return 0; }
运行结果
svg