详解——[蓝桥杯2017初赛]跳蚱蜢

蚱蜢"/>

详解——[蓝桥杯2017初赛]跳蚱蜢

[蓝桥杯2017初赛]跳蚱蜢

• 题目描述
• 建模
• 判重
• 完整代码

题目描述

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

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

建模

直接让蚱蜢跳到空盘，此时有很多只蚂蚱同时跳。如果看成空盘跳到蚱蜢的位置就简单多了，只有一个空盘在跳。
  这个时候应该已经有不少同学看出来是八数码问题了，八数码是经典的BFS问题。如果你想进一步了解八数码，请移步传送门：八数码问题
  题目中已经给蚂蚱编号1-8，此时不妨将空盘编号为0，则有9个数字{0,1,2,3,4,5,6,7,8}，初始状态是“012345678”，终止状态是“087654321”，一共有9！=362880种排列，不算是很多。因为蚂蚱跳的时候必须跳在空盘上，也就只需考虑空盘两边距离为2以内的蚂蚱。

for(int j=i-2;j<=i+2;j++){int k = (j+9)%9;if(k==i) continue;char tmp;tmp=s[i];s[i]=s[k];s[k]=tmp;//此时编号为j的蚂蚱调到了空盘上q.push(node(s,t+1));tmp=s[i];s[i]=s[k];s[k]=tmp;
}

判重

假如不判重，能运行出来吗？
  这里可以提前告诉大家，题目答案为20，本题每一步会有四种情况，那么一共会有4^20=1099511627776种，而其中有效的只有9！=362880种排列，不判重显然是不行的
  有朋友之前跟我说过，蓝桥杯的简单题目就是考STL，我认为还是很有道理的，比赛时可以用map、set判重，我这里就写map

map<string,bool> mp;//创建map

for(int j=i-2;j<=i+2;j++){int k = (j+9)%9;if(k==i) continue;char tmp;tmp=s[i];s[i]=s[k];s[k]=tmp;if(!mp[s]){	//使用map判重mp[s] = true;q.push(node(s,t+1));}tmp=s[i];s[i]=s[k];s[k]=tmp;
}

完整代码

#include<bits/stdc++.h>
using namespace std;struct node
{string s;int t;node(string ss, int tt){s = ss, t = tt;}
};map<string,bool> mp;
queue<node> q;void solve()
{while(!q.empty()){node now = q.front();q.pop();string s = now.s;int t = now.t;if(s == "087654321"){cout<<t<<endl;break;}int i;for(i=0;i<10;i++){if(s[i]=='0') break;}for(int j=i-2;j<=i+2;j++){int k = (j+9)%9;if(k==i) continue;char tmp;tmp=s[i];s[i]=s[k];s[k]=tmp;if(!mp[s]){mp[s] = true;q.push(node(s,t+1));}tmp=s[i];s[i]=s[k];s[k]=tmp;}}
}
int main(){string s = "012345678";q.push(node(s, 0));mp[s] = true;solve();return 0;
}