← 返回题目列表

Codeforces · 2152/B

B. 抓住克鲁格

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

Doran 和 Krug 正在一个由 $$$(n + 1) \times (n + 1)$$$ 个单元格组成的网格上玩游戏,这些单元格的坐标是从 $$$0$$$ 到 $$$n$$$(含)的整数对。克鲁格的目标不是 抓住了 尽可能长时间地由 Doran 提供,而 Doran 的目标是 抓住 克鲁格越早越好。我们说多兰 抓住了 克鲁格,如果它们站在同一个网格单元上。

玩游戏时,Krug 和 Doran 轮流轮流,从 Krug 开始:

  • 克鲁格可以留在同一个单元格中,也可以垂直或水平移动到一个单元格(但是 不 对角线)相邻。正式来说,如果克鲁格当前位于单元格 $$$(a, b)$$$,她可以留在 $$$(a, b)$$$ 或移动到 $$$(a-1, b)、(a, b-1)、(a, b+1)、(a+1, b)$$$。
  • Doran 可以留在同一个单元格中,也可以移动到垂直、水平或对角相邻的单元格。正式来说,如果 Doran 当前位于 $$$(c, d)$$$ 单元格,他可以留在 $$$(c, d)$$$ 或移动到 $$$(c-1, d-1)、(c-1, d)、(c-1, d+1)、(c, d-1)、(c, d+1)、(c+1, d-1)、(c+1, d)、 (c+1,d+1)$$$。
  • 两名玩家都不能走出网格。
显示克鲁格和多兰可能移动的图。字母“K”和“D”代表克鲁格和多兰的当前位置,彩色单元格代表每个玩家在各自回合中可以移动到的可能位置。

克鲁格的 生存时间 被定义为 Doran 的回合数,直到 Doran 捕获 给定玩家起始单元格的 Krug。假设两名球员都发挥最佳水平,求 Krug 的 生存时间 或报告克鲁格可以无限回合生存。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例由一行包含五个整数 $$$n$$$、$$$r_K$$$、$$$c_K$$$、$$$r_D$$$ 和 $$$c_D$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le r_K, c_K, r_D, c_D \le n$$$, $$$(r_K, c_K) \ne (r_D, c_D)$$$) — $$$n$$$ 是网格的大小,$$$(r_K, c_K)$$$ 代表 Krug 的起始单元,$$$(r_D, c_D)$$$ 代表 Doran 的起始单元。

输出

对于每个测试用例,输出 Krug 生存时间 当两名玩家都发挥最佳状态时。如果克鲁格可以无限回合生存,则打印 $$$-1$$$。

示例

输入
复制

7
2 0 0 1 1
3 1 1 0 1
1 1 0 0 1
6 1 3 3 2
9 4 1 4 2
82 64 2 63 2
1000000000 500000000 500000000 1000000000 0

输出
复制

1
3
1
4
2
19
1000000000

注意

第一个测试用例的说明:

Krug 从 $$$(0,0)$$$ 开始,Doran 从 $$$(1,1)$$$ 开始。轮到克鲁格时,她只能移动到 $$$(0,0)$$$、$$$(0,1)$$$ 或 $$$(1,0)$$$。

Doran 从 $$$(1,1)$$$ 开始,一次移动即可到达 $$$3 \times 3$$$ 网格上的任何单元格。因此,无论克鲁格移动到哪里,多兰总能在第一回合移动到她的牢房。克鲁格的生存时间是$$$1$$$。

第二个测试用例说明:

Krug 起始价为 $$$(1,1)$$$,Doran 起始价为 $$$(0,1)$$$。为了在多兰的第一个回合中生存,克鲁格必须移动到多兰无法到达的牢房。唯一的这样的单元格是$$$(2,1)$$$。

克鲁格移动到 $$$(2,1)$$$ 后,Doran 移动到 $$$(1,1)$$$ 以靠近。

现在,克鲁格的第二次移动必须再次移动到 Doran 无法到达的单元格,即 $$$(3,1)$$$。然后 Doran 移动到 $$$(2,1)$$$。

此时,无论克鲁格第三回合移动到哪里,多兰总能到达她的牢房。可以证明,这对于两者来说都是最优策略,因此 Krug 的生存时间为 $$$3$$$。