问题 25631. -- 黄金莲花池

25631: 黄金莲花池

时间限制: 1 Sec  内存限制: 128 MB
献花: 37  解决: 7
[献花][花圈]

题目描述

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

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

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

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

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

输入

第一行:两个用空格分开的整数:MN

第二行到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

提示


最少需要两朵莲花,有三种方式可以放置,



如下 X 所示:



    1
0 0 0 0          1 0 X 0 0          1 0 X 0 0



    3
0 X 0 0          3 0 0 0 0          3 0 0 0 X



    0
0 2 0 0          0 X 2 0 0          0 0 2 0 0




    0 X 0 4 0          0 0 0 4 0          0 0 0 4 0



来源

[献花][花圈]