AcWing 1102. 移动骑士
宋标 Lv5
  2022-08-18 02:30:53 2022-08-18 02:30    

题目

给定一个 的棋盘，以及一个开始位置和终点位置。

棋盘的横纵坐标范围都是 。

将一个国际象棋中的骑士放置在开始位置上，请问将它移动至终点位置至少需要走多少步。

一个骑士在棋盘上可行的移动方式如下图所示：

QQ截图20191016061524.png

输入格式

第一行包含整数 ，表示共有 组测试数据。

每组测试数据第一行包含整数 ，表示棋盘大小。

第二行包含两个整数 用来表示骑士的开始位置坐标 。

第三行包含两个整数 用来表示骑士的终点位置坐标 。

输出格式

每组数据输出一个整数，表示骑士所需移动的最少步数，每个结果占一行。

数据范围

,

输入样例：

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

输出样例：

5
28
0

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import java.util.*;
import java.io.*;

import static java.lang.System.out;

class Main {

    static class Pair {
        int x, y, d;
        public Pair(int x, int y, int d) {
            this.x = x; this.y = y; this.d = d;
        }
    }

    static Scanner sc = new Scanner(new BufferedInputStream(System.in));
    static final int N = 310;
    static int kx, ky, tx, ty;
    static int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1}, dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

    static int bfs(int n) {

        boolean[] st = new boolean[N * N];
        Pair[] q = new Pair[N * N];
        int hh = 0, tt = 0;

        q[tt ++] = new Pair(kx, ky, 0);
        st[kx * n + ky] = true;

        while (tt > hh) {
            Pair t = q[hh ++];

            for (int i = 0; i < 8; ++ i) {
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < n && !st[x * n + y]) {
                    if (x == tx && y == ty) return t.d + 1;
                    st[x * n + y] = true;
                    q[tt ++] = new Pair(x, y, t.d + 1);
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        int T = sc.nextInt();

        while (T -- > 0) {
            int n = sc.nextInt();
            kx = sc.nextInt(); ky = sc.nextInt();
            tx = sc.nextInt(); ty = sc.nextInt();

            if (kx == tx && ky == ty) {
                out.println(0);
            } else {
                out.println(bfs(n));                
            }
        }
    }

}
 评论