Problem 1 Starting with a map represented by a rectangular grid with height h and width w. Cells are numbered (0, 0) in the top left to (h?1, w?1) in the bottom right. Each cell in the grid is either empty or contains an impassable object. All movements on the map are done as a single step to a cell that is adjacent horizontally or vertically. No diagonal movement is permitted.

(a) Write an algorithm that uses a breadth first search to find the length of the shortest path from (0, 0) to (w ? 1, h ? 1). Return ?1 if no such path exists.

(b) What is the worst case complexity for your algorithm? Be sure to specify how the input size is measured and show your work.

(c) Modify your algorithm from part (a) to return the shortest path from (0, 0) to (w ? 1, h ? 1) in addition to its length. How does your change affect the time complexity? How does your change affect the amount of memory required.