题目描述

在一个无限的二维网格上有三个格子，分别标记为 $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$ 个测试用例的答案：从格子 $A$ 到格子 $B$ 的最短路径长度，要求不能经过格子 $F$。

说明/提示

第一组测试用例可能的最短路径示意图。

第二组测试用例可能的最短路径示意图。

由 ChatGPT 4.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

4
6
41
4
4
2
334