最近，无聊的过河船同学发现了一种无聊的迷宫生成算法，这样便可以生成一个大小为N * M的迷宫，如图2所示，请注意，路径只能从迷宫内部穿过，除起点和终点外不得离开迷宫区域。
最近，无聊的过河船同学发现了一种无聊的迷宫生成算法。 算法过程如下： 一个N * M的矩形区域可以看作N * M个单位网格组成。在每个网格中，随机生成一个从右上角到左下角的L型障碍或者从左上角到右下角的R型障碍（障碍可以被看作一条线段）。 图1：两种障碍 这样便可以生成一个大小为N * M的迷宫，如图2所示。 图2：无聊的迷宫 然后过河船同学想知道，是否存在迷宫内的从迷宫上边界到达迷宫的下边界的路径。这当然不容易，但是在胀鱼同学的帮助下，过河船同学很快解决了这个问题。 然而无聊的过河船同学还是忍不住用眼睛去找从迷宫的上边界到达下边界的路径，可是他经常无论怎么找也找不到，即使尝试了所有可能的路径。于是无聊的过河船同学想知道，随机生成（每个位置的障碍是L型和R型的概率都是0.5）一个大小为N * M的迷宫，存在一条从迷宫上边界到达下边界的路径的概率有多大。 请注意，路径只能从迷宫内部穿过，除起点和终点外不得离开迷宫区域。
（图片来源网络，侵删）
