首先,我们创建一个二维数组 dist,用于记录每个位置的最短步数。初始时,将所有位置的步数初始化为-1,表示尚未访问过。
接下来,我们创建一个队列 queue,用于存储待搜索的位置。
我们将起点位置 (sx, sy) 加入队列,并将其步数 dist[sx][sy] 设置为 0。表示起点位置已经访问过,步数为0。
进入循环,直到队列为空为止。在每一次循环中,我们从队列中取出当前位置 (x, y)。
检查当前位置是否为终点位置 (ex, ey),如果是,则说明已经找到了最短路径,直接返回 dist[x][y],即当前位置的步数。
遍历当前位置的所有邻居节点,由于马可以向八个方向跳跃,所以我们遍历所有可能的八个邻居位置。通过计算当前位置 (x, y) 和 dx[]、dy[] 数组的组合,我们可以得到邻居节点的坐标 (nx, ny)。
如果邻居节点 (nx, ny) 在合法的范围内并且尚未访问过(即 dist[nx][ny] == -1),则将其加入队列,并更新其步数为 dist[x][y] + 1,表示从起点到达邻居节点的步数。
当队列为空时,说明无法到达终点位置,返回 -1,表示不存在最短路径。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
static int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
int T = sca.nextInt();
while (T -- > 0) {
int n = sca.nextInt();
int sx = sca.nextInt();
int sy = sca.nextInt();
int ex = sca.nextInt();
int ey = sca.nextInt();
int ans = dfs(n, sx, sy, ex, ey);
System.out.println(ans);
}
}
``
public static int bfs(int n, int sx,int sy, int ex, int ey) {
int[][] dist = new int[n][n];
for (int i = 0; i < n; ++ i) {
Arrays.fill(dist[i], -1);
}
Queue<Pair> queue = new LinkedList<>();
queue.offer(new Pair(sx,sy));
dist[sx][sy] = 0;
while (!queue.isEmpty()) {
Pair cur = queue.poll();
int x = cur.x;
int y = cur.y;
if (x == ex && y ==ey) {
return dist[x][y];
}
for (int i = 0; i < 8; ++ i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == -1) {
queue.offer(new Pair(nx,ny));
dist[nx][ny] = dist[x][y] + 1;
}
}
}
return -1;
}
}