Valid Path in a Grid

You are given a grid consisting of . (free cell) and # (obstacle). The grid has n rows and m columns. Your task is to determine if there is a valid path from the top-left corner (cell (0, 0)) to the bottom-right corner (cell (n-1, m-1)). You may move one cell at a time in the four cardinal directions (up, down, left, right), but you cannot move through cells containing obstacles.

Use an algorithm such as breadth-first search (BFS) to explore possible paths. If a path exists, print possible; otherwise, print impossible.

The mathematical formulation of the path existence can be stated as: \[ \exists \; path \; : \; (0,0) \rightarrow (n-1, m-1) \quad \text{such that every step }(i,j) \rightarrow (i',j') \text{ satisfies } |i-i'|+|j-j'|=1 \text{ and } grid[i'][j'] = '.' \]

inputFormat

The input is provided via standard input (stdin). The first line contains two integers n and m, representing the number of rows and columns in the grid. The following n lines each contain a string of m characters. Each character is either . (a free cell) or # (an obstacle).

outputFormat

Output a single line to standard output (stdout) containing either possible if there exists a valid path from the top-left to the bottom-right corner, or impossible if no such path exists.## sample

5 6
......
.#.#..
.#....
##..#.
....#.

possible