#3353. 「CEOI2020」象棋世界

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

题目译自 CEOI 2020 Day2 T3「Chess Rush

象棋世界是一个 R C 列的棋盘,其中 R \geq C 。所有的行依此编号为 1 R ,所有的列依此编号为 1 C

在象棋世界里,共有五种棋子:兵,车,象,后,王。与现实世界不同的是,骑士精神在象棋世界中已经死亡,因此象棋世界里找不到马。

象棋世界里,每种棋子可以按如下规则进行一步移动:

  • 兵只能向行号增大的方向走一步(从第 r 行到第 r+1 行),且其所处的列不变。
  • 车只能沿水平方向或竖直方向移动。
  • 象只能沿对角线方向移动。
  • 后可以沿水平方向,竖直方向,或对角线方向移动。
  • 王可以向与之相邻的八个格子移动。

为了方便你理解,我们在下图给出了每种棋子的合法移动范围。其中 X 代表该棋子能移动到的位置。

chess.png

最近一段时间,象棋世界发生了不少诡异的事情:某些棋子可能会被不明来源的力量所劫持,随后从象棋世界中消失。在这种情况下,所有棋子都希望能尽快前往他们想要到达的目的地,他们还想知道,在走的步数最少的前提下,到达目的地的方案数有多少。两种方案是不同的,当且仅当这两种方案中有一步经过的格子不同。

在本题中,你需要解决下面这个问题:某个棋子将从第 1 行的第 c_1 列出发,到达第 R 行的第 c_R 列。现在给出这个棋子的类型,以及 c_1,c_R 的值,你需要求出,这个棋子最少需要走多少步,以及在步数最少的前提下,行走方案有多少种。

输入格式

第一行包含三个整数 R,C,Q ,表示象棋世界中棋盘的行数,列数,以及需要回答的询问数。

接下来 Q 行,包含一个字母 T ,代表棋子种类,以及两个整数 c_1,c_R ,代表起点为第 1 行的第 c_1 列,终点为第 R 行的第 c_R 列。

各字母与棋子种类对应关系如下所示:

字母 棋子种类
\texttt{P}
\texttt{R}
\texttt{B}
\texttt{Q}
\texttt{K}

输出格式

对于每个询问,输出两个整数,第一个整数代表从起点到终点需要走的最少步数,第二个整数代表在步数最少的前提下,从起点到终点的方案数。

因为方案数可能很大,请输出其对 10^9+7 取模后的结果。

特别地,若无法从起点到达终点,请输出一行 0 0

样例

样例输入

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

样例输出

0 0
2 2
2 5
2 2
7 393

数据范围与提示

所有测试点均满足: 1 \leq Q \leq 1000 2 \leq C \leq 1000 C \leq R \leq 10^9 T \in \{\texttt{P},\texttt{R},\texttt{Q},\texttt{B},\texttt{K}\} 1 \leq c_1,c_R \leq C

各子任务的约束条件如下:

子任务编号 分值 约束
1 0 样例
2 8 T \in \{\texttt{P},\texttt{R},\texttt{Q}\}
3 15 T=\texttt{B} C,R \leq 100
4 22 T=\texttt{B}
5 5 T=\texttt{K} C,R \leq 100 Q \leq 50
6 8 T=\texttt{K} C,R \leq 100
7 15 T=\texttt{K} C \leq 100
8 20 T=\texttt{K}
9 7 无特殊约束