分值：$200$ 分

题目描述

有一个 $H$ 行 $W$ 列的网格。一开始有一个石头在左上角的格子中。Shik 尝试移动石头到右下角的格子中。每一步，它可以向下、向上、向右或向下（如果那个格子存在）移动石头。允许石头经过一个格子多次（包括左上角和右下角的格子）。

给你一个字符矩阵 $a_{ij}$（$1 \leq i \leq H$，$1 \leq j \leq W$）。在 Shik 完成所有移动操作后，如果石头从来没有经过第 $i$ 行第 $j$ 列的方格，则 $a_{ij}$ 是 #，否则 $a_{ij}$ 是 .。请确定 Shik 是否有可能只使用了向下或者向右的移动操作。

数据范围

• $2 \leq H, W \leq 8$
• $a_{i,j}$ 是 # 或者 .。
• 存在一个 Shik 的移动序列生成这个地图。

输入格式

从标准输入按照如下格式给出：

$H$ $W$

$a_{11}a_{12}$$...$$a_{1W}$

$:$

$a_{H1}a_{H2}$$...$$a_{HW}$

输出格式

如果 Shik 可能只用向右或向下的移动，输出 Possible。否则输出 Impossible。

4 5
##...
.##..
..##.
...##

Possible

这个矩阵可以根据 $7$ 次的移动序列生成：右、下、右、下、右、下、右。

5 3
###
..#
###
#..
###

Impossible

4 5
##...
.###.
.###.
...##

Impossible