LQ0092 跳蚱蜢【BFS】

蚱蜢【BFS】"/>

LQ0092 跳蚱蜢【BFS】

题目来源：蓝桥杯2017初赛 C++ A组B题

题目描述
如图所示： 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？

输出格式
输出一个整数表示答案

问题分析
最短路问题，用BFS来解决。

AC的C++语言程序如下：

/* LQ0092 跳蚱蜢 */#include <iostream>
#include <queue>
#include <unordered_map>using namespace std;const int dir[] = {1, -1, 2, -2};
string start = "12345678X", taget = "87654321X";int bfs()
{unordered_map<string, int> dist;queue<string> q;q.push(start);dist[start] = 0;while (!q.empty()) {string t = q.front();q.pop();if (t == taget) return dist[t];int k = t.find('X'), d = dist[t];for (int i = 0; i < 4; i++) {swap(t[k], t[(k + dir[i] + 9) % 9]);if (dist.count(t) == 0) {q.push(t);dist[t] = d + 1;}swap(t[k], t[(k + dir[i] + 9) % 9]);}}return -1;
}int main()
{cout << bfs() << endl;return 0;
}