程序设计导论：Python语言实践

2.4.6　渗透原理的递归解决方案

如何测试一个系统在一般情况下，即从顶部网格开始到底部网格任一路径（而不仅仅局限于垂直情况）是否渗透？

很显然，我们可以使用一个基于深度优先搜索（depth-first search）的经典递归方案的紧凑程序来解决这个问题。程序2.4.6（percolation.py）是flow()的一种实现，用于基于一个带4个参数的递归函数_flow()计算路径矩阵isFull[][]。递归函数所带的参数包括：网格空置矩阵isOpen[][]，路径矩阵isFull[][]，以及通过行索引i和列索引j指定的网格位置。递归的基本情况是一种满足下列条件的直接返回的递归调用（我们称这种调用为空调用，null call）：

·i或者j超出二维数组的边界。

·网格为阻塞状态（isOpen[i][j]为False）。

·该网格已经标记为全连通状态（isFull[i][j]为True）

归约步骤标记网格为填充状态（filled），并为其四个邻居调用递归函数：isOpen[i+1][j]、isOpen[i][j+1]、isOpen[i][j-1]和isOpen[i-1][j]。为了实现flow()函数，我们针对顶部行的每个网格分别调用递归函数_flow()。递归总会终止，因为每个递归调用要么是空调用，要么标记一个新的网格为全连通状态。通过基于归纳法的参数（和递归程序一样）表明一个网格标记为全连通状态的充分必要条件是，该网格为流通状态且可通过一系列流通邻居网格连接到顶部行的一个网格。

程序2.4.6　渗透检测（percolation.py）

使用本程序中实现的函数替换程序2.4.1中的flow()函数，可获得渗透原理问题的一个基于深度优先搜索的解决方案。调用_flow(isOpen, ...