蓝桥杯2017A java 第二题 跳蚱蜢

蚱蜢"/>

蓝桥杯2017A java 第二题 跳蚱蜢

有9只盘子，排成1个圆圈。

其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8

每只蚱蜢都可以跳到相邻的空盘中，

也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，

并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？

注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

图2. 跳蚱蜢

思路：广搜

package javaa;import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;public class tiao3 {static long yuanshi = 912345678;static long mubiao = 987654321;static int length = 9;static int ans;static int l = 0;static int list[] = {1, 2, -1, -2};static HashSet<Long> hashSet = new HashSet<>();static Queue<jianmo> queue = new LinkedList<>();public static void main(String[] args) {jianmo firstJianmo = new jianmo(yuanshi, 8, 0);hashSet.add(yuanshi);queue.add(firstJianmo);while(!queue.isEmpty()) {System.out.println(l++);jianmo tanchudeJianmo = queue.poll();if (tanchudeJianmo.num == mubiao) {ans = tanchudeJianmo.step;System.out.println(ans);return;}else {jiaru(tanchudeJianmo);}}}public static void jiaru(jianmo tanchude) {for (int i = 0; i < list.length; i++) {int jiaohuanzhishu = (tanchude.ninezhishu + list[i] + length) % 9;int jiaohuangyinzi;if (jiaohuanzhishu == 0) {jiaohuangyinzi = (int) (tanchude.num % 10);}else {jiaohuangyinzi = (int) (tanchude.num % (long)Math.pow(10, jiaohuanzhishu + 1) / Math.pow(10, jiaohuanzhishu));}long jiaohuanghoudeshu = tanchude.num + (jiaohuangyinzi - 9) * (long)Math.pow(10, tanchude.ninezhishu) + (9 - jiaohuangyinzi) * (long)Math.pow(10, jiaohuanzhishu);if (hashSet.add(jiaohuanghoudeshu)) {queue.add(new jianmo(jiaohuanghoudeshu, jiaohuanzhishu, tanchude.step + 1));}}}
}class jianmo{long num;int ninezhishu;int step;public jianmo(long num, int ninezhishu,int step) {// TODO Auto-generated constructor stubthis.num = num;this.ninezhishu = ninezhishu;this.step = step;}
}