P1606 [USACO07FEB] Lilypad Pond G

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 $M$ 行 $N$ 列个方格（$1\le M,N \le 30$）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。 贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。 贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。 约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然，莲花不能放在石头上。 请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法。

第 1 行：两个由空格分隔的整数：$M$ 和 $N$。 第 $2$ 到 $M+1$ 行：第 $i+1$ 行描述了池塘的第 $i$ 行，使用 N 个由空格分隔的整数，这些整数的含义如下：$0$ 表示空水；$1$ 表示已有的荷叶；$2$ 表示岩石；$3$ 表示 Bessie 出发的荷叶；$4$ 表示 Bessie 想要前往的荷叶。

第 1 行：一个整数：所需的最少额外荷叶数量。如果无法帮助 Bessie 跳到她的目的地，输出 -1。 第 2 行：一个整数：放置额外荷叶的所有可能方式的总数。保证这个数能放入一个 $64$ 位有符号整数中。如果第 $1$ 行输出是 $-1$，则不要输出这一行。

池塘被分成四行五列。Bessie 的起点在第二行第一列，目的地是第四行第四列。池塘中有三个荷叶和一块石头。 至少需要两个荷叶，有三种放置方式，如下所示： $$\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} $$