2017年蓝桥杯省赛填空题- 跳蚱蜢

题目

题目链接

题解

BFS（+STL）

最少次数，每次跳跃对次数的贡献都是1，完全可以抽象理解为最短路，所以采用BFS可以直接算出最短长度。

状态转移存在四种，以题中给的状态为例，可以选择2跳到空处、1跳到空处、7跳到空处或8跳到空处。标记一下遇到过的状态，不要再加入队列中了。

代码

#include
#define PIV pair 
using namespace std;

int ans = 0;
vector  target = {0, 8, 7, 6, 5, 4, 3, 2, 1}; // 目标状态 
map  st; // 标记 

vector  exchage (vector  v, int x, int y) {
	swap (v[x], v[y]);
	return v;
}

void bfs () {
	queue  q; // I表示0的位置，V表示状态 
	vector  s;
	s = {0, 1, 2, 3, 4, 5, 6, 7, 8};
	q.push ({0, s});
	st[s] = 1;
	
	while (q.size()) {
		int k = q.size ();
		ans ++;
		for (int i = 0;i