figure grid for exercise write program that computes enough information to output path in the maze give output in the form sen (representing go souththen eastthen northetc if you are using +compiler with windowing packagewrite program that draws the maze andat the press of buttondraws the path suppose that walls in the maze can be knocked downwith penalty of squares is specified as parameter to the algorithm (if the penalty is then the problem is trivial describe an algorithm to solve this version of the problem what is the running time for your algorithm suppose that the maze may or may not have solution describe linear-time algorithm that determines the minimum number of walls that need to be knocked down to create solution (hintuse double-ended queue describe an algorithm (not necessarily linear-timethat finds shortest path after knocking down the minimum number of walls note that the solution to part (awould give no information about which walls would be the best to knock down (hintuse exercise write program to compute word ladders where single-character substitutions have cost of and single-character additions or deletions have cost of specified by the user as mentioned at the end of section this is essentially weighted shortest-path problem explain how each of the following problems (exercises can be solved by applying shortest-path algorithm then design mechanism for representing an inputand write program that solves the problem the input is list of league game scores (and there are no tiesif all teams have at least one win and losswe can generally "prove,by silly transitivity argument