You are given two integers a and k. Grasshopper starts in a point 0 on an OX axis. In one move, it can jump some integer distance, that is not divisible by k, to the left or to the right.What's the smallest number of moves it takes the grasshopper to reach point a? What are these moves? If there are multiple answers, print any of them.给出中文解释及C++代码
时间: 2024-01-31 20:02:40 浏览: 22
这道题目是给定一个整数a和正整数k,有一只草蜢在坐标轴上的0点,每次可以向左或向右跳一个不是k的倍数的整数距离,问草蜢最少要跳几次才能跳到坐标轴上的a点,并输出这些跳的方式。
我们可以使用BFS(广搜)算法来解决这个问题。每次从队列中取出一个位置,向左和向右分别跳一步,如果跳的位置是未访问过的且不是k的倍数,就加入队列中,并记录跳的次数和跳的方向。当跳到a位置时,输出跳的方案即可。
下面是C++代码实现:
```c++
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100005;
bool vis[MAXN][2]; // vis[i][0/1]表示i位置向左/右是否已经访问过
int pre[MAXN][2]; // pre[i][0/1]表示i位置向左/右的上一个位置
int dir[MAXN][2]; // dir[i][0/1]表示从上一个位置到达i位置的方向
int ans[MAXN]; // 记录跳的方案
int a, k;
void bfs() {
queue<int> q;
q.push(0);
vis[0][0] = true; // 从0位置向左跳是已经访问过的,因为没有前一个位置
while (!q.empty()) {
int cur = q.front(); // 当前位置
q.pop();
if (cur == a) // 到达a位置,输出跳的方案
{
int pos = cur;
int i = 0;
while (pos != 0) // 从a位置向前遍历,记录跳的方向
{
ans[i++] = dir[pos][1];
pos = pre[pos][1];
}
for (int j = i - 1; j >= 0; j--) // 倒序输出跳的方向
cout << (ans[j] ? "R" : "L");
return;
}
// 向左跳
int nxt = cur - k;
if (nxt >= 0 && !vis[nxt][0]) // 判断是否越界或已经访问过
{
vis[nxt][0] = true;
pre[nxt][1] = cur; // 记录上一个位置和跳的方向
dir[nxt][1] = 0;
q.push(nxt);
}
// 向右跳
nxt = cur + k;
if (nxt <= a && !vis[nxt][1]) // 判断是否越界或已经访问过
{
vis[nxt][1] = true;
pre[nxt][0] = cur; // 记录上一个位置和跳的方向
dir[nxt][0] = 1;
q.push(nxt);
}
}
}
int main() {
cin >> a >> k;
bfs();
return 0;
}
```