← 返回题目列表

Codeforces · 1797/A

A. 李华与迷宫

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

有一个大小为 $$$n\times m$$$ 的矩形迷宫。将 $$$(r,c)$$$ 表示为从顶部开始的第 $$$r$$$ 行和从左边开始的第 $$$c$$$ 列上的单元格。如果两个单元共享一条边,则它们是相邻的。路径是一系列相邻的空单元格。

每个单元格最初都是空的。李华可以选择一些单元格($$$(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

注意

在测试用例 1 中,您可以在 $$$(1,3), (2,3), (3,2), (4,2)$$$ 上设置障碍。那么从 $$$(2,2)$$$ 到 $$$(3,3)$$$ 的路径将不存在。