[数据结构与算法]八数码难题——bfs(java)

编号为1～8的8个正方形滑块摆成3行3列(有一个格式留空），如图所示。每次可以把与空格相邻的滑块（有公共边才算相邻）.移动到空格中，而它原来的位置就成舍了新的空格。给定葫始高面和目标局面（用0表示空格），你的任务是计算出最少的移动步数。如果无法到达局面，则输出-1。
样例输入：

2 6 4 1 3 7 0 5 8 
8 1 5 7 3 6 4 0 2

代码实现：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class eight_Digital {
	static int[] goal = new int[9];//目标状态数组
	static int[] fa = new int[1000000];//”父亲“编号数组
	static int[] dist = new int[1000000];//距离数组
	static int[][] st = new int[1000000][9];//过程状态数组
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static Set<Integer> vis = new HashSet<Integer>();//存放没一步结果，防止回到原来已经走过的路。
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//3*3样例
		// 2 6 4 1 3 7 0 5 8  初始
		// 8 1 5 7 3 6 4 0 2  goal
		for (int i = 0; i < 9; i++) {
			st[1][i] = sc.nextInt();
		}	
		for (int i = 0; i < 9; i++) {
			goal[i] = sc.nextInt();
		}
		int v=0;
		for (int i = 0; i < 9; i++) v=v*10+goal[i];
		vis.add(v);//add goal
		int ans = bfs();// 分析之后，使用宽度搜索更合适
		if(dist[ans]>0) {
			System.out.println("最小步数：");
			System.out.println(dist[ans]);
			System.out.println(fa[ans]);}
		else 
			System.out.println(0);
		System.out.format("\33[32;4m移动如下：%n");//%n表示换行
		
		int[][] process = new int[dist[ans]+1][9];    //本来dist[ans]为所需的步数，
													//我们第process[0][9]放起始状态，方便构造
		print(process,ans);
		
	}
	/*
	 * 输出 结果
	 */
	private static void print(int[][] process,int ans) {		
		int i=dist[ans]+1;
		while(true) {		
			process[--i] = st[ans];
			if(ans==1)
				break;
			ans = fa[ans];
		}
		for (int j = 0; j < process.length; j++) {
			System.out.format("\33[32;4m第"+j+"步：%n");	
			for (int j2 = 0; j2 < 9; j2++) {
				System.out.print(process[j][j2]+"\t");
				if(j2==2||j2==5) 
					System.out.println();	
			}
			System.out.println();
		}
		
	}
/*
 * 返回 最终结果 fornt 堆首 或 0未找到
 */
	private static int bfs() {
		init_lookup_table();
		int front=1,rear=2;
		
		while(front<rear) {
			int[] s = st[front];
			
			if(Arrays.equals(s, goal)) {
				fa[rear] = front;
				return front;}
			int z;
			for ( z = 0; z < 9; z++) 
				if(s[z]==0) 
					break;
			
			int x = z/3,y=z%3;
			for (int d = 0; d < 4; d++) {
				int newx = x+dx[d];
				int newy = y+dy[d];
				int newz = newx*3+newy;
				if(newx>=0&&newx<3&&newy>=0&&newy<3) {
					for (int i = 0; i <9; i++) 
						st[rear][i] = s[i];
					
					st[rear][newz] =s[z];//每次只有两个位置改变
					st[rear][z] = s[newz];
					
					dist[rear] = dist[front]+1;//再栈首的基础上加一
					
					fa[rear] = front;//给任意一个 fornt，都能fornt = fa[fornt],构造过程
					if(try_to_insert(rear)==1) rear++;
				}//end if
			}// end for
			front++;
		}//end while
		return 0;
	}
/*
 * 初始化
 */
	private static void init_lookup_table() {
		vis.clear();
		for (int i = 0; i < 1000000; i++) {
			dist[i] = 0;	
		}
		
	}
/*
 * 尝试插入 如果集合里面已经有了，则不再插入，否者插入
 */
	private static int try_to_insert(int rear) {
		int v=0;
		for (int i = 0; i < 9; i++) v=v*10+st[rear][i];
		if(vis.contains(v)) return 0;
		vis.add(v);
		return 1;
		
	}

}

结果：


… and so on