Sledgehammer Maze

A maze is a list of strings of equal length, one per row: '.' is open floor and '#' is a wall. You start on the top-left square and want to reach the bottom-right square, moving one square up, down, left or right at a time and never off the edge. Both of those squares are open.

You carry a sledgehammer that can smash at most k walls. Stepping onto a wall square smashes it and uses one swing; that step counts as one move like any other.

Write fewest_moves(maze, k) that returns the fewest moves needed to reach the bottom-right square, or -1 if it cannot be done with at most k smashed walls.

Examples

maze = ['...',
        '##.',
        '...',
        '.##',
        '...']
fewest_moves(maze, 0)               # returns 10
fewest_moves(maze, 1)               # returns 6
fewest_moves(['.#', '#.'], 0)       # returns -1
fewest_moves(['.#', '#.'], 1)       # returns 2

Without the hammer, the first maze is a winding corridor of 10 moves. With one swing you can smash the wall below the start and walk straight down and across: 6 moves.

Constraints

• 1 to 60 rows and 1 to 60 columns.
• 0 <= k <= 60.