题目描述

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成

了M行N列个方格（1 ≤ M, N ≤ 30）。一些格子是坚固得令人惊讶的莲花，还有一些格子是

岩石，其余的只是美丽、纯净、湛蓝的水。

贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花

跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向

移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。

约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。

于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。

当然，莲花不能放在石头上。

请帮助约翰确定必须要添加的莲花的最少数量。在添加莲花最少的基础上，确定贝西从

起点跳到目标需要的最少步数。最后，确定满足添加的莲花数量最少时，步数最少的路径条

数。

输入格式

第一行：两个用空格分开的整数：M和N

第二行到M + 1行：第i + 1行有N个用空格分开的整数，描述了池塘第i行的状态：0 为水，1 为莲花，2 为岩石，3 为贝西所在的起点，4 为贝西想去的终点。

输出格式

第一行：一个整数：需要添加的莲花的最少数目；如果无解，则输出-1

第二行：一个整数：在添加莲花最少的基础上，贝西从起点跳到终点需要的最少步数；如果第一行是-1，不输出这行

第三行：一个整数：在添加莲花最少的基础上，步数等于第二行输出的路径条数；如果第一行是-1，不输出这行

4 8 
0 0 0 1 0 0 0 0 
0 0 0 0 0 2 0 1 
0 0 0 0 0 4 0 0 
3 0 0 0 0 0 1 0 
（池塘分成四行八列，贝西的起点在第四行
第一列，想去的终点在第三行第六列，池塘
里一共有五朵莲花和一块石头）

2
6
2
最少要加两朵莲花，位置如 x 所示：
        0 0 0 1 0 0 0 0          0 0 0 1 0 0 0 0 
        0 x 0 0 0 2 0 1          0 0 0 0 0 2 0 1 
        0 0 0 0 x 4 0 0          0 0 x 0 x 4 0 0 
        3 0 0 0 0 0 1 0          3 0 0 0 0 0 1 0 
贝西至少要跳六步，两种不同的跳法如下：
        0 0 0 C 0 0 0 0          0 0 0 C 0 0 0 0 
        0 B 0 0 0 2 0 F          0 0 0 0 0 2 0 F 
        0 0 0 0 D G 0 0         0 0 B 0 D G 0 0 
        A 0 0 0 0 0 E 0          A 0 0 0 0 0 E 0      ）