← 返回题目列表

Codeforces · 1547/A

A. 有障碍的最短路径

中文机器翻译题面 查看原题

无限二维网格上有三个单元格,标记为 $$$A$$$、$$$B$$$ 和 $$$F$$$。求从 $$$A$$$ 到 $$$B$$$ 的最短路径的长度,如果:

- 一次移动,你可以到达共享一侧的四个相邻单元格中的任何一个;
- 禁止访问单元格$$$F$$$(它是一个障碍)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。每个测试用例之前都有一个空行。

每个测试用例包含三行。第一个包含两个整数 $$$x_A, y_A$$$ ($$$1 \le x_A, y_A \le 1000$$$) - 起始单元格 $$$A$$$ 的坐标。第二个包含两个整数 $$$x_B, y_B$$$ ($$$1 \le x_B, y_B \le 1000$$$) - 终点单元格 $$$B$$$ 的坐标。第三个包含两个整数 $$$x_F, y_F$$$ ($$$1 \le x_F, y_F \le 1000$$$) - 禁止单元格 $$$F$$$ 的坐标。所有细胞都是不同的。

坐标$$$x$$$对应列号,坐标$$$y$$$对应行号(见下图)。

输出

输出 $$$t$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 测试用例的答案:如果不允许访问单元格 $$$F$$$,则从单元格 $$$A$$$ 到单元格 $$$B$$$ 的最短路径的长度。

示例

输入 #1

7

1 1
3 3
2 2

2 5
2 1
2 3

1000 42
1000 1
1000 1000

1 10
3 10
2 10

3 8
7 8
3 7

2 1
4 1
1 1

1 344
1 10
1 1

输出 #1

4
6
41
4
4
2
334

注意

第一个测试用例的可能最短路径示例。

第二个测试用例的可能最短路径示例。