坐标移动(pair+BFS)

 

题目内容：

从一个点移动到另一个点，

1.向前一步，坐标加1；

2.向后一步，坐标减1；

3.跳跃一步，坐标乘2；

求最少多少步；

读入：n，a,b分别表示坐标轴长度，起始点，终点坐标；

输出：一个整数ans；

样例：

输入：10 2 7

输出：3

可以用BFS的原因：步数固定增长。且求最优解

pair的好处：不用手写结构体；

#include
#define int long long
#define endl '\n'
using namespace std;
const int N = 50050;
queueint, int> >q;
bool vis[N];
signed main(){	
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, a, b;
	cin >> n >> a >> b;
	q.push(make_pair(a, 0));//分别代表启示位置，和走的步数；
	vis[a] = true;
	while (!q.empty()) {
		//取出头，开始操作；
		int now = q.front().first;
		int step = q.front().second;
		q.pop();//弹出头；
		if (now == b) {		//结束条件
			cout << step << endl;
			return 0;
		}
		if (now + 1 <= n && !vis[now + 1]) {
			q.push(make_pair(now + 1, step + 1));
			vis[now + 1] = true;
		}
		if (now - 1 >=0 && !vis[now - 1]) {
			q.push(make_pair(now - 1, step + 1));
			vis[now - 1] = true;
		}
		if (now * 2 <= n && !vis[now * 2]) {
			q.push(make_pair(now * 2, step + 1));
			vis[now * 2] = true;
		}
	}
	//q = queue >();//清空
	return 0;
}