Fewest Walls to Knock Down

A renovation crew stands in the top-left cell of a floor plan and must reach the bottom-right cell. The plan is a list of equal-length strings plan; '.' is open floor and '#' is a wall. The crew moves up, down, left or right. Stepping into an open cell is free; stepping into a wall cell means knocking that wall down, which costs 1. The starting cell is never counted, even if it is a wall.

Return the minimum number of walls that must be knocked down.

Examples

Input:  plan = [".#.",
                "##.",
                "..#"]
Output: 2
Explanation: both neighbours of the start are walls, and the target itself is a wall.

Input:  plan = ["..",
                ".."]
Output: 0

Constraints

• 1 <= rows, cols and rows * cols <= 4 * 10**4
• Target O(rows * cols) time.

Goals

• Model a grid as a graph whose edges cost 0 or 1
• Use a deque: push 0-cost moves to the front, 1-cost moves to the back
• Count the target cell if it is itself a wall