题目传送门：点击打开链接
移动 II
|
||||||
| Description | ||||||
| 在坐标轴[0,500]上存在两点A,B。 点A可以多次移动，每次移动需要遵循如下规则： 1.向后移动一步。 2.向前移动一步。 3.跳到当前坐标*2的位置上。
要求：利用宽搜算法编程求解从A移动到B的步数最少的方案，为使答案统一，要求搜索按照规则1、2、3的顺序进行。 |
||||||
| Input | ||||||
| 输入包含多组测试用例。 每组测试用例要求输入两个整数A,B。 |
||||||
| Output | ||||||
| 按要求输出步数最少的方案。 向后走输出"step back"。 向前走输出"step forward"。 跳跃输出"jump"。 对于每组结果需要追加一个空行。 |
||||||
| Sample Input | ||||||
|
||||||
| Sample Output | ||||||
|
||||||
| Source | ||||||
| 2012 Spring Contest 4 - Search Technology | ||||||
| Author | ||||||
| 卢俊达 |
如果只是问步数的话。这题是很简单的。
但是如果要问你路径的话，就要多加思考了。。
从这题，我们可以学习到如何记录广搜路径。。。这真是极大的收货、
这里就直接上代码了。关键的注释，我都打在代码中了。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;#define MM(a) memset(a,0,sizeof(a));int vis[505];///vis数组记录访问情况。int step[505];///这两个数组的作用晚些说明
int step2[505];void bfs(int beg,int ed)
{queue<int>q;q.push(beg);MM(vis);MM(step);vis[beg]=1;while(!q.empty())///广搜基本格式{int temp=q.front();int temp2;q.pop();if(temp==ed){break;}for(int i=1; i<=3; i++)///题目要求按照规则1、2、3的顺序进行。 这点十分重要。不要漏看。{if(i==1){temp2=temp-1;///向后走一步}else if(i==2){temp2=temp+1;///向前走一步}else if(i==3)///向前跳{temp2=temp*2;}if(temp2>=0&&temp2<=500&&vis[temp2]==0)///满足广搜条件{vis[temp2]=1;step[temp2]=temp;///此步很重要，step[temp2]=temp代表temp2这个点是由temp这个点移动过来的。借此步就能记录路径了。q.push(temp2);}}}return;}int main()
{int beg,ed;while(~scanf("%d %d",&beg,&ed)){MM(step2);bfs(beg,ed);///广搜int flag=0;while(ed!=beg)///step2数组用于记录方法{if(step[ed]==ed-1)///ed是由ed-1移动来的。{step2[flag++]=1;/// 向前走一步}else if(step[ed]==ed+1)///ed是由ed+1移动来的。{step2[flag++]=2;///向后走一步}else{step2[flag++]=3;///跳}ed=step[ed];///更新ed的值}for(int i=flag-1; i>=0; i--)///遍历输出{if(step2[i]==1){printf("step forward\n");}else if(step2[i]==2){printf("step back\n");}else{printf("jump\n");}}printf("\n");}return 0;
}