C++解答

/*
	Name: 八数码 
	Date: 14/10/14 20:21
	Description: IDA*
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>

using namespace std;

int now[10];
char c;
int to[10]={0,1,2,3,8,0,4,7,6,5};
int pos0=0,deep=0,h;
int f(){
	int fnow[10];
	int fto[10];
	int tot=0;
	for(int i=1;i<=9;++i){
		fnow[now[i]]=i-1;
		fto[to[i]]=i-1;
    }
	for(int i=1;i<9;++i){
		tot+=abs(fnow[i]/3-fto[i]/3)+abs(fnow[i]%3-fto[i]%3);
	}
	return tot;
}

void dfs(int ans,int pos){
	
	h=f();
	if(h+ans>deep) return;
	if(ans==deep) {
		cout<<ans<<endl;
		exit(0);
	}
	if(pos!=1&&pos!=4&&pos!=7){
		swap(now[pos],now[pos-1]);
		dfs(ans+1,pos-1);
		swap(now[pos],now[pos-1]);	
	}
	if(pos!=3&&pos!=6&&pos!=9){
		swap(now[pos],now[pos+1]);
		dfs(ans+1,pos+1);
		swap(now[pos],now[pos+1]);
	}
	if(pos>3){
		swap(now[pos],now[pos-3]);
		dfs(ans+1,pos-3);
		swap(now[pos],now[pos-3]);
	}
	if(pos<7){
		swap(now[pos],now[pos+3]);
		dfs(ans+1,pos+3);
		swap(now[pos],now[pos+3]);
	}
} 
int main(){
	/*freopen("1.in","r",stdin);
	for(int i=1;i<=9;++i){
		cin>>now[i];
		if(now[i]==0) pos0=i;
	}*/
	for(int i=1;i<=9;++i){
		cin>>c;
		now[i]=(int)c-48;
		if(now[i]==0) pos0=i;
	}
	while(1){
		dfs(0,pos0);
		++deep;
	}
	
}

Java解答

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    int[] dx = {-3,3,-1,1};

    public Main(){
        Scanner sc=new Scanner(System.in);
        String start = sc.nextLine(),end = "123804765";
        // 起始和结束状态
        HashSet<String> judge = new HashSet<>();
        judge.add(start);
        ArrayList<State> AL=new ArrayList<State>();
        AL.add(new State(start.toCharArray(),0));
        while(!AL.isEmpty()){    //System.out.println(index);
            State current=AL.remove(0);
            if(String.valueOf(current.type).equals(end)){
                System.out.println(current.step);
                return;
            }
            int blank;// 空格的位置
            for(blank = 0;blank<9;blank++)if (current.type[blank] == '0') break;
            for (int dt:dx) {
                if ((blank<3 && dt==-3) || (blank>5 && dt==3) || (blank%3==0 && dt==-1) || (blank%3==2 && dt==1)) continue;//不合法的情形，直接跳过
                else {
                    char[] type_new = new char[9];
                    for (int i = 0; i < 9 ; i++)  type_new[i] = current.type[i];
                    type_new[blank] = type_new[blank+dt];
                    type_new[blank+dt] = '0';
                    String newS = String.valueOf(type_new);
                    if(!judge.contains(newS)) {
                        State newState = new State(type_new,current.step+1);
                        AL.add(newState);
                        judge.add(newS);
                    }
                }
            }


        }
    }

    public static void main(String[] args) {
        Main tk=new Main();
    }

    class State{    //状态
        char[] type;  //格局
        int step;   //步数

        public State(char[] type, int step) {
            this.type = type;
            this.step = step;
        }
    }
}