AcWing 1102. 移动骑士--java
原题链接
简单
作者:
Jiang锋时刻
,
2021-01-30 16:19:16
,
所有人可见
,
阅读 307
算法1
Java 代码
public class Knight {
static int N;
static int[][] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 有多少组数据
int size = sc.nextInt();
while (size-- > 0) {
// 表格的长宽
N = sc.nextInt();
visited = new int[N][N];
int[] res = new int[4];
// 起始坐标和终点坐标
for (int i = 0; i < 4; i++) {
res[i] = sc.nextInt();
}
int[] start = {res[0], res[1]};
int[] end = {res[2], res[3]};
System.out.println(knight(start, end));
}
}
public static int knight(int[] start, int[] end) {
// 8个方向坐标
int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
Queue<int[]> queue = new LinkedList();
queue.add(start);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
// 如果当前坐标等于终点坐标, 则直接返回当前坐标的visited值
if (cur[0] == end[0] && cur[1] == end[1]) {
return visited[cur[0]][cur[1]];
}
// 沿8个方向分别遍历
for (int d = 0; d < 8; d++) {
int x = cur[0] + dx[d];
int y = cur[1] + dy[d];
// 如果当前坐标还未访问过
while (x >= 0 && x < N && y >= 0 && y < N && visited[x][y] == 0) {
visited[x][y] = visited[cur[0]][cur[1]] + 1;
queue.add(new int[]{x, y});
}
}
}
return -1;
}
}