Youre trapped in the bottom-left corner of a w h escape room, and need to cross to the door in the upper-right corner to escape. But, the door will only unlock if you follow the correct path. Fortunately, you have directions for the path to follow across the grid cells on the floor, but the directions are incomplete. The partial path is represented as a string composed of the following characters {U, D, L, R, ?}, where each character represents a direction to take along the grid: U = up, D = down, L = left, R = right. The question marks represent unknown steps that you must figure out. You know that the path may not cross the same grid cell twice.

Write a function CompletePath(s, w, h) that takes in three arguments: a string s representing the partial path, and two integers w and h specifying the room size. Your

3

function should return a string that represents the completed path, with all question marks filled in with the correct directions to take you from the bottom-left corner of the grid to the upper-right corner. If no path is possible, your function should return None. Your function should properly error-check all arguments.

For example: in a 5 5 room, if s = "URD?RUU?UR" then your function should return the completed path to exit the room, "URDRRUUUUR".

Here are a few sample test cases:

 CompletePath("?RDRR?UUUR", 5, 5) = "URDRRUUUUR" CompletePath("UURDD?UUR?R?", 6, 4) = "UURDDRUURURR" 

Complete this function in the iPython notebook.