跳蚱蜢 BFS

张开发
• 2026/4/19 3:17:58 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

跳蚱蜢 BFS
跳蚱蜢题目描述本题为填空题只需要算出结果后在代码中使用输出语句将所填结果输出即可。如下图所示有 9 只盘子排成 1 个圆圈。其中 8 只盘子内装着 8 只蚱蜢有一个是空盘。我们把这些蚱蜢顺时针编号为 1 ~ 8。每只蚱蜢都可以跳到相邻的空盘中也可以再用点力越过一个相邻的蚱蜢跳到空盘中。请你计算一下如果要使得蚱蜢们的队形改为按照逆时针排列并且保持空盘的位置不变也就是 1−8 换位2−7换位,…至少要经过多少次跳跃运行限制最大运行时间1s最大运行内存: 128M题目分析该问题本质是在一个环上做“最少步数的状态转换问题”和九宫重排问题本质是一样的是一个最短路径问题用BFS解决代码如下#includebits/stdc.husingnamespacestd;structNode{string s;intstep;};intbfs(string start,string target){queueNodeq;unordered_setstringvis;q.push({start,0});vis.insert(start);while(!q.empty()){autocurq.front();q.pop();if(cur.starget)returncur.step;intposcur.s.find(0);// 空盘位置intn9;// 4种跳法相邻 跨一个vectorintdir{-1,1,-2,2};for(intd:dir){intnpposd;// 环形处理因为是圆圈if(np0)np9;if(np9)np-9;string nxtcur.s;swap(nxt[pos],nxt[np]);if(!vis.count(nxt)){vis.insert(nxt);q.push({nxt,cur.step1});}}}return-1;}intmain(){// 初始状态题目给的一种常见写法string start123405678;// 目标状态逆时针对称空盘不动string target876504321;coutbfs(start,target)endl;return0;}

更多文章