← 返回题目列表

AtCoder · agc007_a

A. 希克和斯通

中文机器翻译题面 查看原题

分数: 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