讨论/题目交流/关于九宫重排问题/
关于九宫重排问题

捕获1.PNG
捕获2.PNG
测试代码:
7 -1 0
3 1 4
5 6 2
答案21
测试代码:
2 5 4
3 0 -1
1 7 6
答案23

共 1 个回复

这是我的代码,答案不正确,多谢 @太阳家的猫 这个大哥帮我分析了,是judge方法出了问题。judge的正确写法应该参考这个文章http://www.doc88.com/p-37037025908.html

package project20;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class chack {
  public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	String start="";
	for(int i=0;i<9;i++) {
		int n=sc.nextInt();
		if(n==-1) {
			n=8;
		}
		start+=String.valueOf(n);
	}
	String end="012345678";
	if(judge(start)) {//判断是否有解,无解直接输出-1
	   System.out.println(find(start,end));
	}else {
	   System.out.println(-1);
	}
  }
  static int[] d= {3,-1,-3,1};//移动方向:3向上,-1向右,1向左,-3向下

 public static boolean judge(String start) {//判断是否有解,!!!!这个方法写错了
	 int cum=0;
	 for(int i=1;i<start.length();i++) {
		 if(start.charAt(i-1)-'0'>start.charAt(i)-'0'&&start.charAt(i)-'0'!=0)
			 cum+=1;
	 }
	 if(cum%2==0) {
	   return true;
	 }else {
		 return false;
	 }
 }
 public static String totry(String deals,int x,int i) {//移动
	 int p = x + d[i];
		if(!(p<0||p>8||(p%3!=x%3&&p/3!=x/3))){
			char a = deals.charAt(p);
			String change = deals.replace('8', '*');
			change = change.replace(a, '8');
			change = change.replace('*', a);
			return change;
		}else {
			 return deals;	
		}
  }

  private static int find(String start, String end) {//求步数
	  int flag=0;
	HashMap<String, int[]> book = new HashMap<String, int[]>();
	Queue<String> task = new LinkedList<String>();
	int[] a= {0,0};
	book.put(start, a);
	task.offer(start);
	if(start.equals(end)) {//是否0步解
		return 0;
	}
	while(task.size()!=0) {//处理数据
		String deals=task.poll();
		int x=0;
		for(;x<deals.length();x++) {//找空格
			if(deals.charAt(x)=='8') {
				break;
			}
		}
		
		for(int i=0;i<d.length;i++) {//移动求解
			String change=totry(deals,x,i);
			if(change.equals(end)) {//找到解时
			    int[] out=book.get(deals);
			    if(flag==0&&out[0]<=25) {//第一次找到解时,移动步数满足
			      if(out[1]<=4) {//左移次数少于等于4次时,最后一步不管是不是左移都可以
			    	  return out[0]+1;
			      }else if(out[1]==5&&i!=3) {//左移次数等于5次时,最后一步不能是左移
			    	  return out[0]+1;
			      }else {
			    	 flag=out[0];//记录第一次得到解前的最短路径-1
			      }
			    }else{//第n次得到解时
			    	if(out[0]<=flag&&out[1]<=4) {//现路径是不是比第一次得到的路径短或相等,同时左移次数是否符合
				    	  return out[0]+1;//由于队列性质,第n次得到解一般是同样的步数长度
				      }else if(out[0]<=flag&&out[1]==5&&i!=3) {
				    	  return out[0]+1;
				      }else if(out[0]>flag) {
				    	  return -1;
				      }
			    }
			}
			if(!book.containsKey(change)&&!change.equals(end)) {
				int[] y=new int[2];
				System.arraycopy(book.get(deals),0,y,0,2);
				if(i==3) {
					y[1]+=1;
				}
				y[0]+=1;
				book.put(change, y);
				task.add(change);				
			}else if(book.containsKey(change)) {//同样的解时,记录步数最少且左移次数最少的情况
				int[] z1=new int[2];            //砍掉左移次数多的树
				System.arraycopy(book.get(change),0,z1,0,2);
				int[] z2=new int[2];
				System.arraycopy(book.get(deals),0,z2,0,2);
				if(z2[0]+1<=z1[0]) {
					if(z2[1]+1<=z1[1]&&i==3) {
						book.remove(change);
						z2[0]+=1;
						z2[1]+=1;
						book.put(change,z2);
					}else if(z2[1]<=z1[1]&&i!=3) {
						book.remove(change);
						z2[0]+=1;
						book.put(change,z2);
					}
				}
                if(z1[0]>25){
                   return -1;
                }
			}
		}
	}
	return -1;
  }
}