观察题目

求最少次数

故可以使用 bfs

• 定义结构体 pos，里面存储格子坐标 now 和需要花费的步数 depth:

struct pos{
	int now;
        int depth;
};

• 定义队列 q，先将 (1,0) 压入队列；
• 取出队首；
• 判断是否合法：如果越界或已经访问过则非法；
• ​若合法，标记为 true​；
• 如果走到 target，输出深度depth；
• 将 (now+1,depth+1), (now−1,depth+1), (2∗now,depth+1) 入队。

过程为初始化、处理非法、判断是否到达、扩展。

AC CODE

#include<iostream>
#include<cstdlib>
#include<queue>
using namespace std;
bool position[5002000];//不要掐1e6，不然当节点编号接近1e6时乘二扩展会RE
int target;
struct pos{
	int now;
	int depth;
};
queue < pos > q;
void bfs() {
	if(target == 1) {
		cout<<"0"<<endl;
		exit(0);
	}
	q.push(pos{1,0});
	while (!q.empty()) {
		pos x=q.front();
		if(position[x.now]||x.now<1||x.now>target){
			q.pop();
			continue;
		}
		position[x.now]=true;
		if(x.now==target) {
			cout<<x.depth<<endl;
			exit(0);
		}
		for(int i=1; i<=3; i++) {
			if(i==1)
				q.push(pos{x.now-1,x.depth+1});
			if(i==2)
				q.push(pos{x.now+1,x.depth+1});
			if(i==3)
				q.push(pos{x.now*2,x.depth+1});
		}
		q.pop();
	}
}
int main() {
	cin>>target;
	bfs();
	return 0;
}