[Usaco2007 Feb]Lilypad Pond 荷叶池塘

为了让奶牛们欣赏风景和锻炼身体，农夫 John 在农场里修建了一个美丽的长方形池塘，并将其划分成 $M$ 行 $N$ 列的方格。部分方格中有石头，部分方格中有结实的荷叶，其余方格中只有清水。

Bessie 想从起点荷叶跳到目标荷叶。她每次跳跃的方式与国际象棋中的马相同，即沿一个方向移动两格，再沿与之垂直的方向移动一格。

有时，Bessie 无法借助现有的荷叶到达目标。农夫 John 可以在清水方格中添加荷叶，但不能在有石头的方格中添加荷叶。

请计算，为使 Bessie 能够从起点到达目标，最少需要添加多少片荷叶，以及添加最少数量荷叶的方案总数。

输入格式

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

接下来 $M$ 行，每行包含 $N$ 个整数。第 $i$ 行中的第 $j$ 个整数表示池塘第 $i$ 行、第 $j$ 列方格的状态：

• $0$ 表示清水；
• $1$ 表示荷叶；
• $2$ 表示石头；
• $3$ 表示 Bessie 的起点；
• $4$ 表示 Bessie 的目标。

输出格式

第一行输出一个整数，表示最少需要添加的荷叶数量。如果不存在可行方案，输出 $-1$。

如果存在可行方案，第二行输出添加最少数量荷叶的方案总数。该数保证可以用 $64$ 位有符号整数表示。

样例输入

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0

样例输出

2
3

样例解释

池塘共有 $4$ 行 $5$ 列。Bessie 位于第 $2$ 行第 $1$ 列，希望到达第 $4$ 行第 $4$ 列。

至少需要添加 $2$ 片荷叶，共有以下 $3$ 种方案：

• 在第 $4$ 行第 $2$ 列和第 $2$ 行第 $3$ 列添加荷叶；
• 在第 $1$ 行第 $3$ 列和第 $3$ 行第 $2$ 列添加荷叶；
• 在第 $1$ 行第 $3$ 列和第 $2$ 行第 $5$ 列添加荷叶。

数据范围

• $1\le M\le 30$；
• $1\le N\le 30$；
• 方案总数可以用 $64$ 位有符号整数表示。

来源与许可

本题为 USACO 2007 February 试题「Lilypad Pond（荷叶池塘）」，题面与测试数据整理自 BZOJ。

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