#P2411. [USACO07FEB] Silver Lilypad Pond S
[USACO07FEB] Silver Lilypad Pond S
题目描述
为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成
了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 )