← 返回题目列表

Codeforces · 1403/C

C. 国际象棋冲刺

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

Chess Land 的神话世界是一个由 $$$R$$$ 行和 $$$C$$$ 列组成的矩形网格,$$$R$$$ 大于或等于 $$$C$$$。其行和列分别从 $$$1$$$ 到 $$$R$$$ 和 $$$1$$$ 到 $$$C$$$ 进行编号。

国际象棋之地的居民在日常语言中通常被称为棋子,并且有 $$$5$$$ 特定类型的棋子在这片土地上漫游:兵、车、象、后和王。与普遍的看法相反,骑士精神在象棋之地早已消亡,因此找不到骑士。

每件作品从一个方格移动到另一个方格的方式都是独一无二的:一步之遥,

- pawn 可以向前移动一行(即从行 $$$r$$$ 到 $$$r+1$$$),而不改变列;
- 车可以向左/向右移动任意数量的列而不更改行,或者向前/向后移动任意数量的行而不更改列;
- 主教可以移动到与其当前占据的方格相交的两条对角线中的任何方格;
- 皇后可以移动到车或主教可以从她的位置移动到的任何方格;
- 国王可以移动到任何 $$$8$$$ 相邻的方格。

最近,国际象棋之地已成为一个危险的地方:穿过该地的棋子可能会被未知力量意外捕获并消失。因此,他们希望尽可能快地(即以尽可能少的步数)到达目的地,并且他们还对使用最少的步数到达目的地的不同方式感兴趣 - 因为更多的可用路径可能意味着被捕获的机会更低。如果两条路径至少在一个访问过的方格中不同,则认为它们是不同的。

对于这个问题,让我们假设棋子正在 $$$1$$$ 行的给定列中进入棋盘,并在 $$$R$$$ 行的给定列中退出棋盘。你的任务是回答 $$$Q$$$ 问题:给定棋子的类型、它进入 $$$1$$$ 行的列以及它必须到达 $$$R$$$ 行中才能退出的列,计算它在 Chess Land 中必须进行的最小移动次数,以及它能够执行此操作的不同方式的数量。

输入

第一行包含三个空格分隔的整数 $$$R$$$、$$$C$$$ 和 $$$Q$$$ $$$(1 \leq Q \leq 1000$$$, $$$2 \leq C \leq 1000$$$ 和 $$$C \leq R \leq 10^9)$$$ – 的行数和列数分别是棋地和题数。然后是 $$$Q$$$ 行。

每行包含

- 一个角色$$$T$$$,对应于所讨论棋子的类型(“P”代表兵,“R”代表车,“B”代表主教,“Q”代表皇后,“K”代表国王);
- 两个整数 $$$c_1$$$ 和 $$$c_R$$$, $$$1\leq c_1,c_R\leq C$$$,表示该片段从 $$$1$$$ 行的第 $$$c_1$$$ 列开始,必须到达 $$$R$$$ 行的第 $$$c_R$$$ 列。

输出

你必须打印 $$$Q$$$ 行,第 $$$i$$$ 行包含两个空格分隔的整数,第 $$$i$$$ 问题的答案:第一个是所需的最小步骤数,第二个是使用此步骤数可用的不同路径的数量。由于答案可能非常大,因此您必须对 $$$10^9+7$$$ 进行模计算。

如果无法到达目标方格,则输出行“0 0”。

示例

输入 #1

8 8 5
P 1 2
R 4 8
Q 2 3
B 3 6
K 5 5

输出 #1

0 0
2 2
2 5
2 2
7 393

注意

评分:
$$$ \begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & 0 & \text{samples}\\ \hline 2 & 8 & T\in\{\text{'P','R','Q'}\}\text{,即所有片段都是兵、车或后} \\ \hline 3 & 15 & T=\text{'B' 和 } \: C,R\leq 100 \\ \hline 4 & 22 & T=\text{'B'} \\ \hline 5 & 5 & T=\text{'K' 和 }\:C,R\leq 100\:\text{和}\:Q\leq 50 \\ \hline 6 & 8 & T=\text{'K' 和 }\:C,R\leq 100\\ \hline 7 & 15 & T=\text{'K' 和 }\:C\leq 100\\ \hline 8 & 20 & T=\text{'K'}\\ \hline 9 & 7 & \text{无附加约束}\\ \hline \end{array} $$$

您可以在此处下载上述示例和附加(更大)示例输入:https://gofile.io/d/GDzwfC