问用Python填充迷宫的死胡同

EN

import doctest
import time

BLOCKED = 1
EMPTY = 0

SMALL_MAZE =  [
    [1, 1, 1, 1, 1],
    [0, 0, 1, 1, 1],
    [1, 0, 0, 0, 0],
    [1, 1, 0, 1, 1],
    [1, 1, 1, 1, 1] ]

BIG_TEXT_MAZE = """
**************************
*                        *
** ********************* *
   *                   * *
*    **** ****************
*       *                 
**************************
"""

SMALL_TEXT_MAZE = """
******************
**   **** *** ****
****       *     *
**   ** **** *****
**** **   **    **
      * **** *****
*******           
******************
"""


def maze_repr(maze):
    """
    Prints a nice textual represenatation of a maze.
    '*' indicates a wall, ' ' a corridor.

    >>> print(maze_repr( [ [1, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 1, 1] ]))
    ****
      **
    *   
    ****
    """
    string_maze = ""
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            string_maze += "*" if maze[y][x] else ' '
        string_maze += "\n"
    return string_maze[:-1]

def read_maze(text_maze):
    """
    The opposite of `maze_repr`, given a textual maze, builds
    a list of lists from it.

    >>> read_maze("****\\n  **\\n*   \\n****")
    [[1, 1, 1, 1], [0, 0, 1, 1], [1, 0, 0, 0], [1, 1, 1, 1]]
    """
    return list(map((lambda row:  [1 if square == '*' else 0 for square in row]),
                    (i for i in text_maze.split("\n") if i)))

def nears(curr_x, curr_y, maze):
    """
    Returns the squares from which you may go doing one
    step in any of the four cardinal directions
    (NORD, EST, WEST, SOUTH).

    The result consists of:
    * 2 squares if (x, y) is on the corner,
    * 3 squares if (x, y) is on the side,
    * 4 squares otherwise.

    >>> list(nears(1, 0, [ [2, 1, 3], [1, 4, 6] ]))
    [3, 4, 2]
    """
    for (x, y) in ( (curr_x + 1, curr_y), (curr_x, curr_y + 1),
                    (curr_x - 1, curr_y), (curr_x, curr_y - 1)):
        try:
            if x >= 0 and y >= 0:
                yield maze[y][x]
        except IndexError:
            pass

def is_dead_end(x, y, maze):
    """
    Is the square at (x, y) of the maze a dead end?
    A wall can not be a dead end.

    Interenstingly enough, using 2 or 1 instead of 3
    creates some nice chambers in the labirith instead of solving it.

    A square circled by 4 walls is also a dead end, in the case of
    solitary closed inacessible rooms in the labirinth.

    >>> is_dead_end(2, 1, read_maze(SMALL_TEXT_MAZE))
    True
    """
    if maze[y][x] == BLOCKED:
        return False
    return list(nears(x, y, maze)).count(BLOCKED) in (3, 4)

def fill_one_dead_end(maze):
    """
    Fills the first encountered dead end of the maze.

    >>> print(maze_repr(fill_one_dead_end(SMALL_MAZE)))
    *****
      ***
    *    
    *****
    *****
    """
    new = maze[:]
    found_dead_end = False
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            if (not found_dead_end) and is_dead_end(x, y, maze):
                found_dead_end = True
                new[y][x] = BLOCKED
            else:
                new[y][x] = maze[y][x]
    return new

def has_at_least_one_dead_end(maze):
    """
    Does the maze have at least one dead end?

    >>> has_at_least_one_dead_end(read_maze(BIG_TEXT_MAZE))
    True
    """
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            if is_dead_end(x, y, maze):
                return True
    return False

def solve_maze(maze, logging = False):
    """
    Solves mazes where the corridors are one wide,
    filling all the dead ends.

    >>> maze = read_maze(SMALL_TEXT_MAZE)
    >>> print(maze_repr(solve_maze(maze)))
    ******************
    ******************
    ****    **********
    **** ** **********
    **** ** **********
         ** **********
    *******           
    ******************
    >>> maze = read_maze(BIG_TEXT_MAZE)
    >>> print(maze_repr(solve_maze(maze)))
    **************************
    **************************
    **************************
       *      ****************
    *    **** ****************
    *    ****                 
    **************************
    """
    if logging:
        print(maze_repr(maze), end="\n\n")
    while has_at_least_one_dead_end(maze):
        maze = fill_one_dead_end(maze)
        if logging:
            print("\n"*50)
            print(maze_repr(maze), end="\n\n")
            time.sleep(0.2)
    return maze

def main():
    solve_maze(read_maze(SMALL_TEXT_MAZE), logging = True)
    solve_maze(read_maze(BIG_TEXT_MAZE), logging = True)
    doctest.testmod()

if __name__ == "__main__":
    main()