[USACO07FEB] Silver Lilypad Pond S

题目描述

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

输入输出格式

输入格式


第一行,输入两个用空格分开的整数:$M$ 和 $N$。 第二行到 $M + 1$ 行:第 $i + 1$ 行有 $N$ 个用空格分开的整数,描述了池塘第 $i$ 行的状态:`0` 为水,`1` 为莲花,`2` 为岩石,`3` 为 Bessie 所在的起点,`4` 为 Bessie 想去的终点。

输出格式


第一行,一个整数,表示需要添加的莲花的最少数目;如果无解,则输出 $-1$。 第二行,一个整数,表示在添加莲花最少的基础上,贝西从起点跳到终点需要的最少步数;如果第一行是 $-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 

输出样例 #1

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 ```