If a maze has two entryways, it is called a perfect maze if there is only one possible rout to get from one entryway to the other. An easy way to find the unique route through the perfect maze, consists of filling up the blind halls until there are no more blind halls. The remaining halls form the route you are looking for.

Assignment

Your assignment consists of finding the unique route that is used to get from one entryway to another in a perfect maze. To do so, you make a class PerfectMaze, that supports the following methods:

1. The initialize method __init__(s) gets a string that represents the maze as a parameter. This string contains only the following characters: hashes ('#'), spaces (' ') and newline characters ('\n'). These last characters indicate the end of a line. You may assume that only the summed up characters occur in the given string, and that all lines contain the same amount of characters. The method saves the maze as a list of lists (a two-dimensional list) with the name data. The initializing method must make this list as an attribute of the object.

2. The method __str__() gets, as usual, no arguments. When it is called, it prints a graphical display of the maze. Use the template below as a template. The maze itself comes from the attribute data.

3. Two methods getCell(t) and setCell(t,c). The first method gets a tuple $$(x,y)$$ as a parameter and print the value of the maze on the box with position $$(x,y)$$. These co-ordinates correspond with the row with number $$x$$, counted from the top, and the column with number $$y$$, counted from the left. The first row and column have number 0. The function setCell works analogous but it asks two parameters: the first is a tuple $$t = (x,y)$$ that corresponds with a set of co-ordinates of the maze. The second parameter is the value that must be appointed to the box. In practice, this is always a string consisting of a single character: a hash or a space.

4. A method numberWalls(t), to which one parameter must be given: a tuple $$t = (x,y)$$ that represents the co-ordinates of a box. Here, you may assume that this box is not situated on the border of the maze. The method prints the number of adjoining walls of this box.

5. A method firstThreeWalls() to which no parameters must be given and that prints a tuple $$t$$. This tuple represents the co-ordinates of the first box in the maze that is not a wall itself, and has exactly three walls as neighbour. To determine the first box with that property, you first go through the rows of the maze from top to bottom and then the columns of the maze, from left to right. If no such box is found, the method must print the value None.

6. A method findRoute() that finds the way in the perfect maze by repeatedly filling up all boxes with three neighbouring walls with a wall, so that there are no more boxes left.

As a start for your code you may depart from the template below:

class PerfectMaze:

    "Representation and manipulation of a perfect maze."

    def __init__(self, s=''):
    def __str__(self):
    def getCell(self, t):
    def setCell(self, t, i):
    def numberWalls(self, t):
    def firstThreeWalls(self):
    def findRoute(self):

Example

>>> s='''########### #
... #     #   # #
... # ### # # # #
... #   #   # # #
... ### ##### # #
... #   # ###   #
... # ### # #####
... # #   # #   #
... # # # # ### #
... # # # #     #
... # # # # # ###
... #   #   #   #
... ########### #'''
>>> d = PerfectMaze(s)
>>> print(d)
13 x 13 maze:
########### #
#     #   # #
# ### # # # #
#   #   # # #
### ##### # #
#   # ###   #
# ### # #####
# #   # #   #
# # # # ### #
# # # #     #
# # # # # ###
#   #   #   #
########### #
>>> d.firstThreeWalls()
(5, 5)
>>> d.getCell((5, 5))
' '
>>> d.setCell((5, 5), '#')
>>> d.getCell((5, 5))
'#'
>>> d.firstThreeWalls()
(6, 5)
>>> d.findRoute()
>>> print(d)
13 x 13 maze:
########### #
#     #   # #
# ### # # # #
#   #   # # #
### ##### # #
#   #####   #
# ###########
# #   #######
# # # #######
# # # #   ###
# # # # # ###
#   #   #   #
########### #