Robot Navigation with Limited Pushes

You are given an n x n grid that represents a map. Each cell in the grid is either free (denoted by a dot .) or blocked by an obstacle (denoted by a hash #). The robot starts at the top‐left corner (cell (0,0)) and must reach the bottom‐right corner (cell (n-1, n-1)). The robot can move in the four cardinal directions: up, down, left, and right.

In addition to normal moves through free cells, you are allowed to perform a limited number of pushes (up to p times). A push is defined as follows: if the adjacent cell in the moving direction contains an obstacle (#) and the cell immediately beyond it in the same direction exists and is free (.), the robot can push the obstacle aside, effectively treating the obstacle cell as accessible. Each such push decrements your available push count by one.

Your task is to determine whether the robot can reach the destination cell using at most p pushes.

Note: The destination is located at \( (n-1, n-1) \). A move that uses a push is only valid if the cell beyond the obstacle is within bounds and free (i.e. a .).

inputFormat

The input is given via standard input (stdin). The first line contains two integers (n) and (p) separated by a space, where (n) is the dimension of the grid and (p) is the number of allowed pushes. The following (n) lines each contain a string of length (n), representing a row of the grid. Each character is either a dot ('.') or a hash ('#').

outputFormat

Output a single line to standard output (stdout) with either "YES" if the robot can reach the bottom-right corner using at most (p) pushes, or "NO" otherwise.## sample

5 1
.###.
.#.#.
.#.#.
.#.#.
...#.

YES