九宫重排－－蓝桥杯国赛历年真题

标题：九宫重排     如图1的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成图2所示的局面。     我们把图1的局面记为：12345678.     把图2的局面记为：123.46758     显然是按从上到下，从左到右的顺序记录数字，空格记为句点。     本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。 例如： 输入数据为： 12345678. 123.46758 则,程序应该输出： 3 再如： 输入： 13524678. 46758123. 则，程序输出： 22 资源约定： 峰值内存消耗（含虚拟机） < 64M CPU消耗  < 2000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

思路：将九个格子按从上到下从左到右生成一个字符串，当某个格子为空(.)时，使用队列，按广度优先遍历的方法依次移动此时可以移动的格子，知道第一次找到目标字符串为止

package 历届国赛; import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.Scanner; import java.util.List; public class 九宫重排 { static String yl,yh;//移动前和移动后的字符串 static int st = 0;//步数 static HashSet<String>hh = new HashSet();//记录递归中的字符串 static List<gz>list = new ArrayList(); static List<String>l = new ArrayList(); static int[][]w_m = {//当第n个格子为空时，哪个格子可以移动 {-1}, {2,4}, {1,3,5}, {2,6}, {1,5,7}, {2,4,6,8}, {3,5,9}, {4,8}, {5,7,9}, {6,8} }; static int move_num(String s){//哪个格子是空格 for(int i=0;i<s.length();i++){ if(s.charAt(i) == '.') return i+1; } return -1; } static String move(String y,int m,int n){//y为移动前,从m移动到n,返回移动后字符串 char[]c = y.toCharArray(); char mm = c[n-1]; c[n-1] = c[m-1]; c[m-1] = mm; return String.valueOf(c); } static class gz{//宫格类 int step;//步数 String now;//代表当前宫格的字符串 gz(int s,String n){ this.step = s; this.now = n; } } //用队列，当前空格位置，所有可移动的一次入队再出队，类似于广度优先遍历 static void bfs(){ hh.add(yl); gz g = new gz(0,yl); list.add(g);//将yl等所有的字符串封装进gz类（因为列表中每一步的步数值都必须独立） while(!list.isEmpty()){ gz now_ = list.remove(0);//取出第一个; if(now_.now.equals(yh)){ System.out.println(now_.step); break; } int n = move_num(now_.now); for(int i = 0;i<w_m[n].length;i++){//所有可以移动的格子 String temp = move(now_.now,w_m[n][i],n); if(!hh.contains(temp)){ int s = now_.step+1; gz g_ = new gz(s,temp); hh.add(temp); list.add(g_); } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); yl = sc.next(); yh = sc.next(); bfs(); } }