寒假培训：白银莲花池-USACO 2007（洛谷 P2411）

白银莲花池

题目背景

(Silver Lilypad Pond, USACO 2007 Feb)

题目描述

为了使奶牛们能够进行休闲活动并增强体能，农夫约翰设计了一个精致的池塘。这个矩形水池被划分成M行N列的网格（1 ≤ M, N ≤ 30）。其中部分格子生长着结实的莲花，另一些则被岩石占据，其余区域则是清澈湛蓝的水域。

贝西正在学习芭蕾舞，她站在一片莲花上，希望跳到另一片莲花上。她的跳跃只能在莲花之间进行，既不能落水，也不能跳到岩石上。

贝西的舞步类似于象棋中马的走法：每次移动时，先横向移动一格再纵向移动两格，或者先纵向移动两格再横向移动一格。因此，在某些情况下，她最多可以有八个不同的跳跃方向。

约翰一直在观察贝西的练习过程，并发现有时她无法抵达目标位置，原因是路径中缺少必要的荷叶。因此他决定增设一些莲花以帮助贝西完成跳跃任务。出于节约原则，约翰希望新增的莲花数量尽可能少。

当然，新增的莲花不能放置在岩石上。

请协助约翰计算必须增设的最少莲花数量，并在此基础上确定贝西从起点跳至终点所需的最少步数。最后，在满足最少新增莲花的前提下，找出步数最少的所有可行路径数目。

输入输出格式

输入格式：

第一行包含两个由空格分隔的整数：M和N

第二行至第M + 1行中，第i +