[Usaco2007 Feb]Lilypad Pond

Farmer John 建造了一个美丽的长方形池塘，供奶牛们观赏和锻炼。池塘被划分为 $M$ 行 $N$ 列的正方形网格。部分格子中生长着坚固的莲花，部分格子中有岩石，其余格子则是水。

贝茜正在池塘中练习跳跃。她从指定的起点出发，希望到达指定的终点。每次跳跃的方式与中国象棋中的马相同：横向移动 $1$ 格、纵向移动 $2$ 格，或者横向移动 $2$ 格、纵向移动 $1$ 格。因此，她每次最多有 $8$ 个可选的落点。

贝茜只能落在莲花上，不能落入水中，也不能落在岩石上。由于现有的莲花可能不足以构成一条从起点到终点的路径，Farmer John 可以在水面格子中添加莲花，但不能在岩石上添加。

请依次求出：

• 为使贝茜能够从起点跳到终点，至少需要添加多少朵莲花；
• 在添加莲花数量最少的前提下，贝茜从起点到终点最少需要跳跃多少步；
• 同时满足添加莲花数量最少且跳跃步数最少的跳跃路径共有多少条。

输入格式

第一行包含两个整数 $M,N$，分别表示池塘的行数和列数。

接下来 $M$ 行，每行包含 $N$ 个整数，描述池塘中各格子的状态：

• $0$ 表示水；
• $1$ 表示莲花；
• $2$ 表示岩石；
• $3$ 表示贝茜的起点；
• $4$ 表示贝茜的终点。

输出格式

如果无论如何都无法使贝茜到达终点，仅输出一行一个整数 $-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

数据范围

• $1\le M\le 30$；
• $1\le N\le 30$。

来源与许可

本题为 USACO 2007 February 试题「Lilypad Pond」，题面与测试数据整理自 BZOJ。

样例 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