A22610.Lilypad Pond G
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了 M 行 N 列个方格(1≤M,N≤30)。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。
贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。
贝西的舞步很像象棋中的马步:每次总是先横向移动一格,再纵向移动两格,或先纵向移动两格,再横向移动一格。最多时,贝西会有八个移动方向可供选择。
约翰一直在观看贝西的芭蕾练习,发现她有时候不能跳到终点,因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。一贯节俭的约翰只想添加最少数量的莲花。当然,莲花不能放在石头上。
请帮助约翰确定必须要添加的莲花的最少数量,以及有多少种放置这些莲花的方法。
输入格式
第一行两个用空格分开的整数 M和N。
第二行到 M+1 行,第 i+1 行有 N 个用空格分开的整数,描述了池塘第 i 行的状态:
0 为水,1 为莲花,2 为岩石,3 为贝西所在的起点,4 为贝西想去的终点。
输出格式
第一行一个整数,需要增加的最少莲花数;如果无解,输出 −1
第二行输出放置这些莲花的方案数量,保证这个数字可用一个 64 位的有符号整数,表示。
特别地,如果第一行是 −1,不要输出第二行。
输入输出样例
输入#1
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0 0 0 0 4 0
输出#1
2 3
说明/提示
样例解释
池塘分成四行五列,贝西的起点在第二行第一列,想去的终点在第四行第四列,池塘里一共有三朵莲花和一块石头。
最少需要两朵莲花,有三种方式可以放置,
如下 X 所示:
1000030X00002000X040,10X00300000X20000040,10X003000X0020000040