分数: 200 点
问题陈述
我们有一个网格 H 行和 W 列。最初,左上角的牢房里有一块石头。希克正试图将石头移到右下角的牢房。在每一步中,他都可以将石头向左、上、右或下移动一个单元格(如果存在这样的单元格)。石头有可能多次访问一个单元格(包括右下角和左上角的单元格)。
给你一个字符矩阵 a_{ij} (1 \leq i \leq H, 1 \leq j \leq W)。 Shik完成所有移动动作后, a_{ij} is # 如果石头曾经位于 i第行和 j移动过程中的第 3 列。否则, a_{ij} is .。请确定 Shik 是否有可能在所有步骤中只使用向右和向下的移动。
约束
- 2 \leq H, W \leq 8
- a_{i,j} 是
#or.. - Shik 存在生成地图的有效移动序列 a.
输入
输入由标准输入按以下格式给出:
H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}
输出
如果 Shik 可能只使用向右和向下移动,则打印 Possible。否则,打印 Impossible.
示例输入 1
4 5 ##... .##.. ..##. ...##
示例输出 1
Possible
矩阵可以由 7- 移动顺序:右、下、右、下、右、下、右。
示例输入 2
5 3 ### ..# ### #.. ###
示例输出 2
Impossible
示例输入 3
4 5 ##... .###. .###. ...##
示例输出 3
Impossible