Write a program that reads a rectangular maze from standard input in the following format, where '#' represents a wall:
######## # # # # # # # # # # ## ## # ########
The maze will be surrounded by walls.
The program should print True if the maze is connected, i.e. every two empty squares in the maze are connected by some path. Otherwise print False.
Write a function that takes a 2-dimensional array of booleans representing a maze. There will be no wall in the upper-left or lower-right corner.
The procedure should print out the maze, indicating the shortest path from the upper-left corner to the lower-right corner. For example, the output might look like this:
..###### #.# # #.# # # #...# # ## ....# ######..
If no such path exists, print the maze without any path.
Write a function prefix_parse() that takes a string containing an expression in prefix notation such as '+ * 2 5 * 3 6'. The function should return an expression tree in which leaves are integers, and interior nodes are represented using this class:
class OpExpr:
def __init__(self, left, op, right):
self.left = left # left child: en expression tree
self.op = op # op: an operator such as '+'
self.right = right # right child: an expression treeRepeat the previous exercise, but parse infix expressions such as '((2 * 5) + (3 * 6))'. Assume that expressions are fully parenthesized.
Consider a limping knight on a chessboard. On odd moves, it moves like a pawn, i.e. one square forward (or stays in place if it is at the top of the board). On even moves, it moves like a normal knight in chess. Write a function limping_dist(start, end) that returns the smallest number of moves that the knight must make to go from a given starting square to a given ending square. Assume that squares are pairs of coordinates, i.e. (1, 1) is the upper-left corner of the chessboard and (8, 8) is the lower-right corner.
Three missionaries and three cannibals are on the west bank of a river. They have a canoe that can hold two people, and they all must cross to the east bank of the river. There may never be more cannibals than missionaries on either side of the river, or the cannibals will eat the missionaries. Further, the canoe must have at least one person on board to cross the river. Write a program to find and print a sequence of crossings that will take the party safely across.