A2897. Lilypad Pond G
编程题
省选/NOI-
知识点
题目描述
为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 $M$ 行 $N$ 列个方格（$1 \le M,N \le 30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。
贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。
贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。
约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然，莲花不能放在石头上。
请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法。
贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。
贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。
约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然，莲花不能放在石头上。
请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法。
输入格式
第一行两个用空格分开的整数 $M$和$N$。
第二行到 $M+1$ 行，第 $i+1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：
$0$ 为水，$1$ 为莲花，$2$ 为岩石，$3$ 为贝西所在的起点，$4$ 为贝西想去的终点。
第二行到 $M+1$ 行，第 $i+1$ 行有 $N$ 个用空格分开的整数，描述了池塘第 $i$ 行的状态：
$0$ 为水，$1$ 为莲花，$2$ 为岩石，$3$ 为贝西所在的起点，$4$ 为贝西想去的终点。
输出格式
第一行一个整数，需要增加的最少莲花数；如果无解，输出 $−1$
第二行输出放置这些莲花的方案数量，保证这个数字可用一个 $64$ 位的有符号整数，表示。
特别地，如果第一行是 $−1$，不要输出第二行。
第二行输出放置这些莲花的方案数量，保证这个数字可用一个 $64$ 位的有符号整数，表示。
特别地，如果第一行是 $−1$，不要输出第二行。
输入输出样例
输入 #1
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0 0 0 0 4 0
输出 #1
2 3
说明/提示
### 样例解释
池塘分成四行五列，贝西的起点在第二行第一列，想去的终点在第四行第四列，池塘里一共有三朵莲花和一块石头。
最少需要两朵莲花，有三种方式可以放置，
如下 $\verb!X!$ 所示：
$$\begin{bmatrix} \verb!10000! \\ \verb!30X00! \\ \verb!00200! \\ \verb!0X040! \\ \end{bmatrix},\begin{bmatrix} \verb!10X00! \\ \verb!30000! \\ \verb!0X200! \\ \verb!00040! \\ \end{bmatrix},\begin{bmatrix} \verb!10X00! \\ \verb!3000X! \\ \verb!00200! \\ \verb!00040! \\ \end{bmatrix} $$
池塘分成四行五列，贝西的起点在第二行第一列，想去的终点在第四行第四列，池塘里一共有三朵莲花和一块石头。
最少需要两朵莲花，有三种方式可以放置，
如下 $\verb!X!$ 所示：
$$\begin{bmatrix} \verb!10000! \\ \verb!30X00! \\ \verb!00200! \\ \verb!0X040! \\ \end{bmatrix},\begin{bmatrix} \verb!10X00! \\ \verb!30000! \\ \verb!0X200! \\ \verb!00040! \\ \end{bmatrix},\begin{bmatrix} \verb!10X00! \\ \verb!3000X! \\ \verb!00200! \\ \verb!00040! \\ \end{bmatrix} $$