#----------------------------------------------------------------------- # percolation.py #----------------------------------------------------------------------- import stdio import stdarray #----------------------------------------------------------------------- # isOpen is a matrix that represents the open sites of a system. # isFull is a partially completed matrix that represents the full sites # of that system. Update isFull by marking every site of that system # that is open and reachable from site (i, j). def _flow(isOpen, isFull, i, j): n = len(isFull) if (i < 0) or (i >= n): return if (j < 0) or (j >= n): return if not isOpen[i][j]: return if isFull[i][j]: return isFull[i][j] = True _flow(isOpen, isFull, i+1, j ) # Down. _flow(isOpen, isFull, i , j+1) # Right. _flow(isOpen, isFull, i , j-1) # Left. _flow(isOpen, isFull, i-1, j ) # Up. #----------------------------------------------------------------------- # isOpen is a matrix that represents the open sites of a system. # Compute and return a matrix that represents the full sites of # that system. def flow(isOpen): n = len(isOpen) isFull = stdarray.create2D(n, n, False) for j in range(n): _flow(isOpen, isFull, 0, j) return isFull #----------------------------------------------------------------------- # isOpen is matrix that represents the open sites of a system. Return # True if that system percolates, and False otherwise. def percolates(isOpen): # Compute the full sites of the system. isFull = flow(isOpen) # If any site in the bottom row is full, then the system # percolates. n = len(isFull) for j in range(n): if isFull[n-1][j]: return True return False #----------------------------------------------------------------------- # Read from standard input a boolean matrix that represents the # open sites of a system. Write to standard output a boolean # matrix representing the full sites of the system. Then write # True if the system percolates and False otherwise. def main(): isOpen = stdarray.readBool2D() stdarray.write2D(flow(isOpen)) stdio.writeln(percolates(isOpen)) #isOpen = stdarray.readBool2D() #stdarray.write2D(flow(isOpen)) #draw(isOpen, False) #stddraw.setPenColor(stddraw.BLUE) #draw(flow(isOpen), True) #stdio.writeln(percolates(isOpen)) #stddraw.show() if __name__ == '__main__': main() #----------------------------------------------------------------------- # python percolation.py < test5.txt # 5 5 # 0 1 1 0 1 # 0 0 1 1 1 # 0 0 0 1 1 # 0 0 0 0 1 # 0 1 1 1 1 # True # python percolation.py < test8.txt # 8 8 # 0 0 1 1 1 0 0 0 # 0 0 0 1 1 1 1 1 # 0 0 0 0 0 1 1 0 # 0 0 0 0 0 1 1 1 # 0 0 0 0 0 1 1 0 # 0 0 0 0 0 0 1 1 # 0 0 0 0 1 1 1 1 # 0 0 0 0 0 1 0 0 # True