蓝桥杯历届试题-九宫重排 （Java代码）

解题思路:

注意事项:

参考代码:

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

public class T1426 {
	static int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			String begin = in.next(), end = in.next();
			int t = begin.indexOf(".");
			Queue<State> queue = new LinkedList<State>();
			queue.offer(new State(begin, t / 3, t % 3, 0));
			HashSet<String> set = new HashSet<String>();
			set.add(begin);
			int ans = 0;
			s: while (!queue.isEmpty()) {
				State tmp = queue.poll();
				for (int i = 0; i < 4; i++) {
					int tx = tmp.x + dir[i][0], ty = tmp.y + dir[i][1];
					if (tx >= 0 && tx < 3 && ty >= 0 && ty < 3) {
						StringBuilder sb = new StringBuilder(tmp.s);
						char c = sb.charAt(3 * tx + ty);
						sb.setCharAt(3 * tx + ty, sb.charAt(3 * tmp.x + tmp.y));
						sb.setCharAt(3 * tmp.x + tmp.y, c);
						String str = sb.toString();
						if (str.equals(end)) {
							ans = tmp.cnt + 1;
							break s;
						}
						if (!set.contains(str)) {
							set.add(str);
							queue.offer(new State(sb.toString(), tx, ty, tmp.cnt + 1));
						}
					}
				}
			}
			System.out.println(ans);
		}
		in.close();
	}

}

class State {
	String s;
	int x, y;
	int cnt;

	public State(String s, int x, int y, int cnt) {
		super();
		this.s = s;
		this.x = x;
		this.y = y;
		this.cnt = cnt;
	}

}