Knight Moves 解题报告

这道题是找出一个骑士去访问另一个骑士的最少移动的步数，可以用bfs解决，做这道题首先要了解马的走法，马先走直线在走斜线，共有8种走法如下图:

D4可以走周围标红的位置，可以用一个数组来储存.

算发：用bfs可以解决。

public class Main {

	private static int[][] position = new int[8][2];
	private static int[][] chessboard = new int[8][8];

	public Main() {
		initPosition();
	}

	/**
	 * 初始化马可以走的方向
	 */
	private static void initPosition() {
		position[0][0] = -2;
		position[0][1] = -1;
		position[1][0] = -2;
		position[1][1] = 1;
		position[2][0] = -1;
		position[2][1] = -2;
		position[3][0] = -1;
		position[3][1] = 2;
		position[4][0] = 1;
		position[4][1] = -2;
		position[5][0] = 2;
		position[5][1] = -1;
		position[6][0] = 1;
		position[6][1] = 2;
		position[7][0] = 2;
		position[7][1] = 1;
	}

	private static int[] getRC(String s) {
		int[] rc = new int[2];
		rc[0] = Integer.valueOf(String.valueOf(s.charAt(1))) - 1;
		rc[1] = s.charAt(0) - 'a';
		return rc;
	}

	/**
	 * 广度搜索算法
	 * 
	 * @param s1
	 * @param s2
	 */
	public static void bsf(String s1, String s2) {
		int[] rc = getRC(s1);
		int formR = rc[0];
		int formC = rc[1];
		// System.out.println(formR + " ," + formC);
		rc = getRC(s2);
		int toR = rc[0];
		int toC = rc[1];
		// System.out.println(toR + " ," + toC);
		LinkedList<Point> queue = new LinkedList<Point>();

		Point p = new Point();
		p.r = formR;
		p.c = formC;
		p.steps = 0;
		queue.addLast(p);
		chessboard[p.r][p.c] = 1;
		p = null;

		while (!queue.isEmpty()) {
			p = queue.getFirst();
			queue.removeFirst();
			if (p.r == toR && p.c == toC) {
				System.out.println("To get from " + s1 + " to " + s2
						+ " takes " + p.steps + " knight moves.");
				break;
			}
			for (int i = 0; i < 8; ++i) {
				Point pp = new Point();
				pp.r = p.r + position[i][0];
				pp.c = p.c + position[i][1];
				pp.steps = p.steps + 1;
				if (pp.r >= 0 && pp.c >= 0 && pp.r <= 7 && pp.c <= 7
						&& chessboard[pp.r][pp.c] == 0) {
					queue.addLast(pp);
					chessboard[pp.r][pp.c] = 1;
				}
				pp = null;
			}
			p = null;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		initPosition();
		while (sc.hasNext()) {
			chessboard = null;
			chessboard = new int[8][8];
			String s1 = sc.next();
			String s2 = sc.next();
			Main.bsf(s1, s2);
		}
	}

}

class Point {
	int r;
	int c;
	int steps;
}