{"problem":{"name":"[EGOI 2022] Superpiece / 超级棋子","description":{"content":"你有一个无限大的棋盘。在本题中，棋盘是一个无限大的二维方格，每个方格用 $(r,c)$ 表示，分别代表行和列。目前棋盘上有唯一一个棋子，叫做**超级棋子**。你有你的超级棋子的合法移动列表，它是一个非空字符串，是 `QRBNKP` 的子序列。在每个回合中，超级棋子可以作为给定的棋子之一移动。超级棋子初始位于 $(a,b)$，请求出到达 $(c,d)$ 的最少移动次数。 在本题中可能用到的国际象棋","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9322"},"statements":[{"statement_type":"Markdown","content":"你有一个无限大的棋盘。在本题中，棋盘是一个无限大的二维方格，每个方格用 $(r,c)$ 表示，分别代表行和列。目前棋盘上有唯一一个棋子，叫做**超级棋子**。你有你的超级棋子的合法移动列表，它是一个非空字符串，是 `QRBNKP` 的子序列。在每个回合中，超级棋子可以作为给定的棋子之一移动。超级棋子初始位于 $(a,b)$，请求出到达 $(c,d)$ 的最少移动次数。\n\n在本题中可能用到的国际象棋规则如下：\n\n共有六种棋子：皇后、车、象、马、国王、兵。他们的移动方式如下：\n\n- **皇后**（`Q`）可以移动到同行、同列、同对角线的方格。形式化地，对于任意整数 $k\\ne 0$，皇后可以从 $(a,b)$ 移动到 $(a+k,b),(a,b+k),(a+k,b+k),(a+k,b-k)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/1e4lh43e.png)\n\n- **车**（`R`）可以移动到同行、同列的方格。形式化地，对于任意整数 $k\\ne 0$，车可以从 $(a,b)$ 移动到 $(a+k,b),(a,b+k)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/mwo8ut9o.png)\n\n- **象**（`B`）可以移动到同对角线的方格。形式化地，对于任意整数 $k\\ne 0$，象可以从 $(a,b)$ 移动到 $(a+k,b+k),(a+k,b-k)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/dhfo04af.png)\n\n- **马**（`N`）可以移动一个 `L` 形，也就是：先在一个方向移动两格，再在与之垂直的方向移动一格。形式化地，马可以从 $(a,b)$ 移动到 $(a+1,b+2),(a+1,b-2),(a+2,b+1),(a+2,b-1),(a-2,b+1),(a-2,b-1),(a-1,b+2),(a-1,b-2)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/jyxiv4s0.png)\n\n- **国王**（`K`）可以移动到相邻的八个格子。形式化地，国王可以从 $(a,b)$ 移动到 $(a,b+1),(a,b-1),(a+1,b),(a-1,b),(a+1,b+1),(a+1,b-1),(a-1,b+1),(a-1,b-1)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qhzd2gzf.png)\n\n- **兵**（`P`）可以向上移动一格。形式化地，兵可以从 $(a,b)$ 移动到 $(a+1,b)$。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/g0dhy9au.png)\n\n请注意，你可能知道的关于国际象棋的其他规则并不适用于本题；请只使用上面列出的那些规则。\n\n## Input\n\n第一行一个整数 $q$，表示数据组数。之后每两行描述一组数据：\n\n- 每组数据的第一行一个非空字符串，是超级棋子的合法移动列表。这个字符串是 `QRBNKP` 的一个子集，所有字符**按相同顺序**出现。换句话说，它是 `QRBNKP` 的一个子序列。\n- 每组数据的第二行四个整数 $a,b,c,d$——超级棋子的初始和目标位置。保证 $(a,b)\\ne (c,d)$，也就是初始位置和目标位置不同。\n\n## Output\n\n对于每组数据，输出一行一个整数 $m$，表示最少移动次数。如果不可能到达目标位置，输出 $-1$。\n\n[samples]\n\n## Background\n\nDay 2 Problem B.\n\n题面译自 [EGOI2022 superpiece](https://stats.egoi.org/media/task_description/2022_superpiece_en.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例 $1$ 解释**\n\n在第一组数据中，我们需要从 $(3,3)$ 走到 $(5,1)$，合法移动有马、国王、兵。有很多种需要两次移动的方案，例如：\n\n- 兵走到 $(4,3)$，马走到 $(5,1)$。\n- 马走到 $(5,2)$，国王走到 $(5,1)$。\n- 国王走到 $(4,2)$，国王走到 $(5,1)$。\n\n不存在少于两次移动的方案——我们需要象或者皇后才能做到。\n\n在第二组数据中，我们需要从 $(2,6)$ 走到 $(5,3)$。同样地，最优方案需要两次移动。此时，每一步都必须是马，利用 $(4,5)$ 或 $(3,4)$ 作为中转站。\n\n---\n\n**样例 $2$ 解释**\n\n在第一组数据中，我们需要从 $(2,8)$ 走到 $(3,6)$。只能按照象的方式走棋，这是不可能的。\n\n在第二组数据中，我们需要从 $(2,8)$ 走到 $(5,5)$，只能按照象的方式走棋。可以在两次移动内实现，例如，利用 $(4,4)$ 作为中转站。\n\n---\n\n**样例 $3$ 解释**\n\n在第一组数据中，我们需要从 $(3,3)$ 走到 $(4,5)$，只能按照皇后的方式走棋。可以利用 $(4,4)$ 为中转站两次移动到达。\n\n在第二组数据中，我们需要从 $(4,1)$ 走到 $(1,4)$，只能按照皇后和车的方式走棋。可以一次移动到达。\n\n---\n\n**数据范围**\n\n对于全部数据，$1\\le q\\le 10^3$，$-10^8\\le a,b,c,d\\le 10^8$。\n\n- 子任务一（$12$ 分）：保证存在 `Q`，保证不存在 `N`。\n- 子任务二（$9$ 分）：保证存在 `QN`。\n- 子任务三（$13$ 分）：保证存在 `R`，保证不存在 `Q`。\n- 子任务四（$8$ 分）：保证只存在 `B`。\n- 子任务五（$6$ 分）：保证存在 `B`，保证不存在 `QR`。\n- 子任务六（$31$ 分）：保证只存在 `N`。\n- 子任务七（$8$ 分）：保证存在 `N`，保证不存在 `QRB`。\n- 子任务八（$7$ 分）：保证存在 `K`，保证不存在 `QRBN`。\n- 子任务九（$6$ 分）：保证只存在 `P`。\n\n注意子任务**并不**按难度顺序排序。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9322","tags":["2022","O2优化","EGOI（欧洲/女生）"],"sample_group":[["2\nNKP\n3 3 5 1\nNKP\n2 6 5 3","2\n2"],["2\nB\n2 8 3 6\nB\n2 8 5 5","-1\n1"],["2\nQ\n3 3 4 5\nQR\n4 1 1 4","2\n1"]],"created_at":"2026-03-03 11:09:25"}}