首页 > 代码库 > 2016蓝桥杯省赛C/C++A组第二题 跳蚱蜢
2016蓝桥杯省赛C/C++A组第二题 跳蚱蜢
题意：有9只盘子，排成1个圆圈。 其中8只盘子内装着8只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1~8 每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。 请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？ 注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。
分析：结果是20。
#include<bits/stdc++.h>using namespace std;set<string> st;int deal(string s){ int len = s.size(); for(int i = 0; i < len; ++i){ if(s[i] == ‘0‘) return i; }}int bfs(){ queue<string> q; queue<int> step; q.push("012345678"); step.push(0); while(!q.empty()){ string s = q.front(); q.pop(); int tmpstep = step.front(); step.pop(); int id = deal(s); string tmps = s; int tmpid = (id + 1) % 9; tmps[id] = s[tmpid]; tmps[tmpid] = s[id]; if(!st.count(tmps)){ if(tmps == "087654321") return tmpstep + 1; st.insert(tmps); q.push(tmps); step.push(tmpstep + 1); } tmpid = (id + 2) % 9; tmps = s; tmps[id] = s[tmpid]; tmps[tmpid] = s[id]; if(!st.count(tmps)){ if(tmps == "087654321") return tmpstep + 1; st.insert(tmps); q.push(tmps); step.push(tmpstep + 1); } tmpid = (id + 8) % 9; tmps = s; tmps[id] = s[tmpid]; tmps[tmpid] = s[id]; if(!st.count(tmps)){ if(tmps == "087654321") return tmpstep + 1; st.insert(tmps); q.push(tmps); step.push(tmpstep + 1); } tmpid = (id + 7) % 9; tmps = s; tmps[id] = s[tmpid]; tmps[tmpid] = s[id]; if(!st.count(tmps)){ if(tmps == "087654321") return tmpstep + 1; st.insert(tmps); q.push(tmps); step.push(tmpstep + 1); } } return -1;}int main(){ printf("%d\n", bfs()); return 0;}
2016蓝桥杯省赛C/C++A组第二题 跳蚱蜢
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。