o-p-p-o2023提前批0715-第三题 国际象棋

Posted on | In |
Words count in article: 1.3k | Reading time ≈ 7

小欧获得了国际象棋中“象”和”马”的能力，她在一个无穷大的平面直角坐标系中，每一步可以效仿国际象棋中 的”象”和”马”跳一步。

如下图，小红初始坐标为$(x，y)$时，只跳一步时可以跳到以下

1.$(x+k，y+k)$，$k$是任意整数。

2.$(x+k,y-k)$，$k$是任意整数。

3.$(x+a,y+b)$.其中$|a|+|b|=3$且$1<=a,b<=2.$

小欧想知道，自己初始坐标为$x1，y1，$他跳到$x2,y2$最少需要跳多少步？共有t次询问

输入描述

第一行输入一个整数$t(1<=t<=100)$表示询问组数

接下来$t$行，每行四个整数$x1,y1,x2,y2$

$-10^9<=x1,y1,x2,y2<=10^9$

输出描述

一个整数，代表最小的步数。

示例：

1

分析：

难度：中等

  • 方法 一：数学 时间复杂度O(t)
1
如果两点之间的 x 和 y 的差值为奇数，那么它们之间的 Manhattan 距离一定是 3，可以通过象走法到达；如果差值为偶数，那么 Manhattan 距离一定是 2，可以通过马走法到达。因此，在这个问题中，我们可以直接计算两点之间的 x 和 y 的差值，然后根据差值的奇偶性判断最少需要多少步才能到达另一个点。
  • 方法二：BFS
1
（BFS）遍历所有可能的路径，直到找到最短路径为止。为了实现马和象的走法，我们需要分别对马和象进行遍历。在遍历时，我们使用了一个 dist 哈希表来记录每个点到起点的最短距离，如果一个点没有被遍历过，我们就将其放入队列中，并更新其距离。最后返回终点的距离即可。

代码

  • C++

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
#include <iostream>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>

using namespace std;

int main() {
	int T;
	cin >> T;
	
	while (T --) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int dx = abs(x1 - x2);
 		int dy = abs(y1 - y2);
 		
 		if (dx < dy) swap(dx, dy);
 		if (dx == dy) {
		 	if (dx % 2 == 0)
		 		cout << 2 << endl;
	 		else
	 			cout << 3 << endl;
		 } 
		 else
		 	cout << 2 << endl;
		
	}
	
	return 0;
}
  • java
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
import javax.swing.plaf.synth.SynthTextAreaUI;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        while (T-- > 0) {
            String[] a = in.readLine().split(" ");
            int dx = Integer.parseInt(a[0]) - Integer.parseInt(a[2]);
            int dy = Integer.parseInt(a[1]) - Integer.parseInt(a[3]);

            if (dx < dy) {
                int tmp = dx;
                dx = dy;
                dy = tmp;
            }

            if (dx == dy) {
                if (dx % 2 == 0)
                    System.out.println(2);
                else
                    System.out.println(3);
            }
            else {
                System.out.println(2);
            }
        }
    }
}
  • Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
t = int(input())

for i in range(t):
    x1, y1, x2, y2 = map(int, input().split())

    dx = abs(x1 - x2)
    dy = abs(y1 - y2)

    if dx < dy:
        dx, dy = dy, dx

    if dx == dy:
        if dx % 2 == 0:
            print(2)
        else:
            print(3)
    else:
        print(2)
  • Golang
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
package main

import (
	"fmt"
	"math"
)

func main() {
	var t int
	fmt.Scan(&t)

	for i := 0; i < t; i++ {
		var x1, y1, x2, y2 int
		fmt.Scan(&x1, &y1, &x2, &y2)

		dx := abs(x1 - x2)
		dy := abs(y1 - y2)

		if dx < dy {
			dx, dy = dy, dx
		}

		if dx == dy {
			if dx%2 == 0 {
				fmt.Println(2)
			} else {
				fmt.Println(3)
			}
		} else {
			fmt.Println(2)
		}
	}
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
  • BFS
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package main

import (
	"bufio"
	"fmt"
	"os"
	"math"
)

type point struct {
	x, y int
}

var (
	dx = []int{1, 1, -1, -1, 2, 2, -2, -2}
	dy = []int{1, -1, 1, -1, 2, -2, 2, -2}
)

func bfs(s, t point) int {
	dist := make(map[point]int)
	dist[s] = 0

	q := []point{s}
	for len(q) > 0 {
		curr := q[0]
		q = q[1:]

		if curr == t {
			return dist[curr]
		}

		// 马走法
		for i := 0; i < 8; i++ {
			nx, ny := curr.x+dx[i], curr.y+dy[i]
			if abs(nx-t.x)+abs(ny-t.y) == 3 {
				next := point{nx, ny}
				if _, ok := dist[next]; !ok {
					dist[next] = dist[curr] + 1
					q = append(q, next)
				}
			}
		}

		// 象走法
		for k := 1; ; k++ {
			nx, ny := curr.x+k, curr.y+k
			if abs(nx-t.x) > k || abs(ny-t.y) > k {
				break
			}
			next := point{nx, ny}
			if _, ok := dist[next]; !ok {
				dist[next] = dist[curr] + 1
				q = append(q, next)
			}
		}
		for k := 1; ; k++ {
			nx, ny := curr.x+k, curr.y-k
			if abs(nx-t.x) > k || abs(ny-t.y) > k {
				break
			}
			next := point{nx, ny}
			if _, ok := dist[next]; !ok {
				dist[next] = dist[curr] + 1
				q = append(q, next)
			}
		}
		for k := 1; ; k++ {
			nx, ny := curr.x-k, curr.y+k
			if abs(nx-t.x) > k || abs(ny-t.y) > k {
				break
			}
			next := point{nx, ny}
			if _, ok := dist[next]; !ok {
				dist[next] = dist[curr] + 1
				q = append(q, next)
			}
		}
		for k := 1; ; k++ {
			nx, ny := curr.x-k, curr.y-k
			if abs(nx-t.x) > k || abs(ny-t.y) > k {
				break
			}
			next := point{nx, ny}
			if _, ok := dist[next]; !ok {
				dist[next] = dist[curr] + 1
				q = append(q, next)
			}
		}
	}

	return -1
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
	var t int
	fmt.Scan(&t)

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	for i := 0; i < t; i++ {
		var x1, y1, x2, y2 int
		scanner.Scan()
		fmt.Sscan(scanner.Text(), &x1)
		scanner.Scan()
		fmt.Sscan(scanner.Text(), &y1)
		scanner.Scan()
		fmt.Sscan(scanner.Text(), &x2)
		scanner.Scan()
		fmt.Sscan(scanner.Text(), &y2)

		s := point{x1, y1}
		t := point{x2, y2}
		fmt.Println(bfs(s, t))
	}
}
0%