試題 算法訓練 跳馬

使用廣度優先搜索，首次抵達結束位置即為結果，或者走不到對應的點位，則輸出 -1；
解題步驟

1. 數據輸入
2. 數據初始化（棋盤初始化為無窮大，表示無法跳到此處）
3. 將開始的位置置為 0，表示 0 步就可以到達這個位置，并將初始位置壓入隊列
4. 遍歷隊列，取出當前位置
5. 從當前位置可以到達的位置（8 個）判斷是否降低了步數，若降低步數，則將當前位置數據壓入隊列
6. 重復 4-5，直至隊列為空或目標點位已抵達
7. 判斷步數，無法抵達置為 -1

馬的位置判斷：

馬有八面威風，就是八個可以走的點位
若馬的初始點位在 \((i, j)\)，則可以走的點位：

1. \((i-2, j-1)\)
2. \((i-1, j-2)\)
3. \((i+1, j-2)\)
4. \((i+2, j-1)\)
5. \((i+2, j+1)\)
6. \((i+1, j+2)\)
7. \((i-1, j+2)\)
8. \((i-2, j+1)\)

還要加上越界的判斷

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author HuaWang135608
 * @date 2023.03.15 10:26:13
 * @description [試題 算法訓練 跳馬](http://lx.lanqiao.cn/problem.page?gpid=T2987)
 */

public class Main {

	public static void main(String[] args) {
		int[][] chessbord = new int[9][9];
		int src_bi, src_bj, src_ei, src_ej;
		
		// 數據輸入
		try (Scanner sc = new Scanner(System.in)) {
			src_bi = sc.nextInt();
			src_bj = sc.nextInt();
			src_ei = sc.nextInt();
			src_ej = sc.nextInt();
		}
		
		// 數據處理
		// 初始化棋盤，代表跳到當前位置的步數是無窮大
		for (int[] row : chessbord) {
			Arrays.fill(row, Integer.MAX_VALUE);
		}
		// 以隊列的形式壓入下一步可以跳到的位置
		int front = 0, rear = 0;
		int[][] queue = new int[64][3];
		queue[rear][0] = src_bi;
		queue[rear][1] = src_bj;
		chessbord[src_bi][src_bj] = queue[rear++][2] = 0;
		// 隊列為空或已抵達對應位置則退出循環（廣度優先，首次抵達就是最優解）
		while (front!=rear && chessbord[src_ei][src_ej]==Integer.MAX_VALUE) {
			int i = queue[front][0];
			int j = queue[front][1];
			int v = queue[front++][2] + 1;
			if (front == queue.length) {
				front = 0;
			}
			
			// 若可以到達此處且步數少于已有的步數，則將當前位置壓入隊列，并更新步數
			if (i>2 && j>1 && chessbord[i-2][j-1]>v) {
				queue[rear][0] = i - 2;
				queue[rear][1] = j - 1;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i - 2][j - 1] = v;
			}
			if (i>1 && j>2 && chessbord[i-1][j-2]>v) {
				queue[rear][0] = i - 1;
				queue[rear][1] = j - 2;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i - 1][j - 2] = v;
			}
			if (i<8 && j>2 && chessbord[i+1][j-2]>v) {
				queue[rear][0] = i + 1;
				queue[rear][1] = j - 2;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i + 1][j - 2] = v;
			}
			if (i<7 && j>1 && chessbord[i+2][j-1]>v) {
				queue[rear][0] = i + 2;
				queue[rear][1] = j - 1;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i + 2][j - 1] = v;
			}
			if (i<7 && j<8 && chessbord[i+2][j+1]>v) {
				queue[rear][0] = i + 2;
				queue[rear][1] = j + 1;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i + 2][j + 1] = v;
			}
			if (i<8 && j<7 && chessbord[i+1][j+2]>v) {
				queue[rear][0] = i + 1;
				queue[rear][1] = j + 2;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i + 1][j + 2] = v;
			}
			if (i>1 && j<7 && chessbord[i-1][j+2]>v) {
				queue[rear][0] = i - 1;
				queue[rear][1] = j + 2;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i - 1][j + 2] = v;
			}
			if (i>2 && j<8 && chessbord[i-2][j+1]>v) {
				queue[rear][0] = i - 2;
				queue[rear][1] = j + 1;
				queue[rear++][2] = v;
				if (rear == queue.length) {
					rear = 0;
				}
				chessbord[i - 2][j + 1] = v;
			}
		}
		int res = chessbord[src_ei][src_ej];
		// 判斷是否能跳到
		if (res == Integer.MAX_VALUE) {
			res = -1;
		}
		
		System.out.println(res);
	}
	
}