1998: 黄金莲花池

【问题描述】

为了让奶牛们娱乐和锻炼，农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格（1≤M, N≤30）。一些格子是坚固得令人惊讶的莲花，还有一些格子是岩石，其余的只是美丽、纯净、湛蓝的水。

   贝西正在练习芭蕾舞，她站在一朵莲花上，想跳到另一朵莲花上去，她只能从一朵莲花跳到另一朵莲花上，既不能跳到水里，也不能跳到岩石上。

   贝西的舞步很像象棋中的马步：每次总是先横向移动一格，再纵向移动两格，或先纵向移动两格，再横向移动一格。最多时，贝西会有八个移动方向可供选择。

   约翰一直在观看贝西的芭蕾练习，发现她有时候不能跳到终点，因为中间缺了一些荷叶。   于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。   当然，莲花不能放在石头上。

   请帮助约翰确定必须要添加的莲花的最少数量，以及有多少种放置这些莲花的方法。

【输入格式】

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

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

【输出格式】

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

第二行：放置这些莲花的方案数量，保证这个数字不会超过一个64位的有符号整数，如果第一行是-1，不要输出第二行

【输入样例】

4 5 
1 0 0 0 0 
3 0 0 0 0 
0 0 2 0 0 
0 0 0 4 0

【输出样例】

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

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

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

第二行：放置这些莲花的方案数量，保证这个数字不会超过一个64位的有符号整数，如果第一行是-1，不要输出第二行

4 5 
1 0 0 0 0 
3 0 0 0 0 
0 0 2 0 0 
0 0 0 4 0

2
3