Li Hua and Maze

题意翻译

有一个大小为 $n\times m$ 的矩形迷宫。称两个格子相邻，当且仅当它们有一条公共边。定义一条路径为若干相邻空格子的序列。 每个格子初始为空。李华可以在若干个格子中放置障碍物。他希望知道最少需要放置多少个障碍物使得不存在一条从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的路径。 假如你是李华，请解决这一问题。 （[全场中文题面](https://www.cnblogs.com/ruierqwq/p/CF1797-CHN-statement.html)）

题目描述

There is a rectangular maze of size $ n\times m $ . Denote $ (r,c) $ as the cell on the $ r $ -th row from the top and the $ c $ -th column from the left. Two cells are adjacent if they share an edge. A path is a sequence of adjacent empty cells. Each cell is initially empty. Li Hua can choose some cells (except $ (x_1, y_1) $ and $ (x_2, y_2) $ ) and place an obstacle in each of them. He wants to know the minimum number of obstacles needed to be placed so that there isn't a path from $ (x_1, y_1) $ to $ (x_2, y_2) $ . Suppose you were Li Hua, please solve this problem.

输入输出格式

输入格式

The first line contains the single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The first line of each test case contains two integers $ n,m $ ( $ 4\le n,m\le 10^9 $ ) — the size of the maze. The second line of each test case contains four integers $ x_1,y_1,x_2,y_2 $ ( $ 1\le x_1,x_2\le n, 1\le y_1,y_2\le m $ ) — the coordinates of the start and the end. It is guaranteed that $ |x_1-x_2|+|y_1-y_2|\ge 2 $ .

输出格式

For each test case print the minimum number of obstacles you need to put on the field so that there is no path from $ (x_1, y_1) $ to $ (x_2, y_2) $ .

输入输出样例

输入样例 #1

3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6

输出样例 #1

4
2
3

说明

In test case 1, you can put obstacles on $ (1,3), (2,3), (3,2), (4,2) $ . Then the path from $ (2,2) $ to $ (3,3) $ will not exist. 

题目大意：
李华有一个 $n \times m$ 大小的矩形迷宫。两个格子相邻是指它们有一条公共边。路径定义为一系列相邻的空格子。迷宫初始时所有格子都是空的，李华可以在除了 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之外的格子中放置障碍物。他想知道最少需要放置多少个障碍物，使得从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 不存在路径。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。
- 每个测试用例的第一行包含两个整数 $n, m$（$4 \le n, m \le 10^9$），表示迷宫的大小。
- 每个测试用例的第二行包含四个整数 $x_1, y_1, x_2, y_2$（$1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m$），表示起点和终点的坐标。
- 保证 $|x_1 - x_2| + |y_1 - y_2| \ge 2$。

输出格式：
- 对于每个测试用例，输出一个整数，表示需要放置的最少障碍物数量，使得从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 不存在路径。

输入输出样例：
输入样例 #1：
```
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6
```
输出样例 #1：
```
4
2
3
```题目大意： 李华有一个 $n \times m$ 大小的矩形迷宫。两个格子相邻是指它们有一条公共边。路径定义为一系列相邻的空格子。迷宫初始时所有格子都是空的，李华可以在除了 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之外的格子中放置障碍物。他想知道最少需要放置多少个障碍物，使得从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 不存在路径。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试用例的数量。 - 每个测试用例的第一行包含两个整数 $n, m$（$4 \le n, m \le 10^9$），表示迷宫的大小。 - 每个测试用例的第二行包含四个整数 $x_1, y_1, x_2, y_2$（$1 \le x_1, x_2 \le n, 1 \le y_1, y_2 \le m$），表示起点和终点的坐标。 - 保证 $|x_1 - x_2| + |y_1 - y_2| \ge 2$。 输出格式： - 对于每个测试用例，输出一个整数，表示需要放置的最少障碍物数量，使得从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 不存在路径。 输入输出样例： 输入样例 #1： ``` 3 4 4 2 2 3 3 6 7 1 1 2 3 9 9 5 1 3 6 ``` 输出样例 #1： ``` 4 2 3 ```