atcoder#AGC007A. [AGC007A] Shik and Stone

[AGC007A] Shik and Stone

分值:200200

题目描述

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

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

数据范围

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

输入格式

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

HH WW

a11a12a_{11}a_{12}......a1Wa_{1W}

::

aH1aH2a_{H1}a_{H2}......aHWa_{HW}

输出格式

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

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

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

5 3
###
..#
###
#..
###
Impossible
4 5
##...
.###.
.###.
...##
Impossible