NOI 2.5.《仙岛求药》题解（C++版）

NOI2.5.2727 仙岛求药 题解(C++)

这道题目实在令人头疼，作者几乎被折磨得不行，气得我差点说不出话来。。。(以下省略2147483647字)。唉，不说这些了，直接上题目吧；

题目

2727:仙岛求药

总时间限制: 1000ms 内存限制: 65536kB
描述
少年李逍遥的婶婶生病了，王小虎建议他前往仙灵岛，向仙女姐姐寻求仙丹以救治婶婶。虽然性格叛逆，但李逍遥十分孝顺，于是他踏入了仙灵岛，在经历重重困难后抵达岛屿中心，发现仙药被安置在迷阵的最深处。该迷阵由M×N个方格构成，其中部分方格内存在能够瞬间击败李逍遥的怪物，而另一些则是安全区域。如今李逍遥希望尽快找到仙药，显然他需要避开那些有怪物的区域，并选择经过最少数量的方格路径。此外，在终点处还会有神秘人物等待着他。现在需要你协助他达成这一目标。
下图展示了迷阵的一个示例以及李逍遥寻得仙药所走的路线.

输入
测试数据包含多组案例。每组案例的起始为两个非零整数 M 与 N，二者均不超过20。其中 M 表示迷宫的行数，N 表示迷宫的列数。随后将输入 M