网站网络营销推广,网站创建域名,asp网站 换模板,还有哪些方法让网站更加利于seo解题思路#xff1a; 这题如果我们考虑蚱蜢跳#xff0c;有很多蚱蜢#xff0c;有很多情况#xff0c;所以我们让空盘跳#xff0c;这样就简化题目了#xff0c;然后我们化圆为直#xff0c;将题目的情况看成字符串012345678#xff0c;最后要变成087654321#xff0c…
解题思路 这题如果我们考虑蚱蜢跳有很多蚱蜢有很多情况所以我们让空盘跳这样就简化题目了然后我们化圆为直将题目的情况看成字符串012345678最后要变成087654321这样题目就变得跟[蓝桥杯2017初赛]青蛙跳杯子 一样了唯一的区别就是这个是个圆所以在012345678这个字符串中0往左跳会跳到8的位置故需要用环形数组我们用map存储字符串来标记。
关键点 1.关于环形的数组前移动和后移动可能会溢出下标。解决方法是转移后的坐标公式为 原坐标改变量数组长度%数组长度 2.map标记圆盘在跳。
代码如下
#include iostream
#include queue
#include map
#include cstring
using namespace std;
string a, b;
int len;
int dian;//原坐标改变量数组长度%数组长度
int dx[] {1, -1, 2, -2};struct node {string str;int dian;int step;node(string str1, int dian1, int step1) {str str1;dian dian1;step step1;}
};int bfs() {mapstring, int st;queuenodeq;q.push(node(a, dian, 0));st[a] 1;while (q.size()) {node t q.front();q.pop();if (t.str b) {return t.step;}for (int i 0; i 4; i) {int dianf (t.dian dx[i] len) % len;//环形数组if (dianf 0 || dianf len)continue;string strf t.str;char hhh strf[t.dian];strf[t.dian] strf[dianf];strf[dianf] hhh;if (st.count(strf) 0) {q.push(node(strf, dianf, t.step 1));st[strf] 1;}}}}int main() {a 012345678;b 087654321;len a.length();dian 0;//0在a中的位置cout bfs() endl;return 0;
}#include iostream
#include queue
#include cstring
#include map
using namespace std;
string a 012345678;
string b 087654321;struct node {string s;int dian;int p;
};int dx[] {1, -1, 2, -2};void bfs(node start) {queuenodeq;mapstring, intmp;q.push(start);mp[start.s] 1;while (q.size()) {node t q.front();q.pop();if (t.s b) {cout t.p endl;return ;}for (int i 0; i 4; i) {int dians (t.dian dx[i] 9) % 9;if (dians 0 || dians 9 )continue;string ss t.s;char hh ss[t.dian];ss[t.dian] ss[dians];ss[dians] hh;if (mp.count(ss) 0) {mp[ss] 1;q.push({ss, dians, t.p 1});}}}
}int main() {node start {a, 0, 0};bfs(start);return 0;
}
