[AGC007A] Shik and Stone

题意翻译

## 题目描述 有一个纵 $ H $ 行,横 $ W $ 列的格子状棋盘。开始时,棋盘左上角的格子有一个马(不是象棋意义的马)。Shik 将会操纵它上下左右移动,从而到达右下角的格子。此时,马能够经过同一个格子多次(含左上角和右下角的格子)。 给出 $ H $ 行字符串,如果第 $ i $ 行第 $ j $ 列的字符为 `#` ,则表示马在移动过程中至少通过了此格一次(左上角和右下角的格子一定会通过至少一次)。当 $ a_{i,j} $ 为 `.` 时,表示马在移动过程中并没有经过此格。 请判断:马是否可能每次移动都向下或向右。 ## 数据范围 - $ 2 \leq H,W \leq 8 $ 。 - $ a_{i,j} $ 一定是 `#` 或 `.`。 - 对于所有数据,马一定能够到达右下角的格子。 ## 输入 输入按以下标准: $$ H \space \space W $$ $$ a_{11}a_{12} ... a_{1W} $$ $$ : $$ $$ a_{H1}a_{H2} ... a_{HW} $$ ## 输出 如果移动过程中存在马只向下或向右移动的可能性,则输出 ``Possible``,否则输出 ``Impossible``。 (样例见原题面)

题目描述

[problemUrl]: https://atcoder.jp/contests/agc007/tasks/agc007_a 縦 $ H $ 行、横 $ W $ 列のマス目に区切られた盤面があります。 はじめ、駒が左上隅のマスに置かれていました。 シックはこの駒を $ 1 $ マスずつ上下左右に動かし、右下隅のマスに移動させました。 このとき、駒が同じマスを複数回通った可能性もあります(左上隅や右下隅のマスも含む)。 縦横に並んだ文字 $ a_{ij} $ ($ 1\ \leq\ i\ \leq\ H $, $ 1\ \leq\ j\ \leq\ W $) が与えられます。 $ a_{ij} $ が `#` のとき、駒が移動する過程で $ i $ 行 $ j $ 列目のマスを一度以上通ったことを表します(左上隅や右下隅のマスは必ず通ったものとして扱います)。 $ a_{ij} $ が `.` のとき、駒が $ i $ 行 $ j $ 列目のマスを一度も通らなかったことを表します。 移動する過程で、駒が常に右または下に動いていた可能性があるか判定してください。

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ A_{11}A_{12} $$ ... $$ A_{1W} $ $ : $ $ A_{H1}A_{H2} $$ ... $$ A_{HW} $

输出格式


移動する過程で、駒が常に右または下に動いていた可能性があれば `Possible` 、なければ `Impossible` と出力せよ。

输入输出样例

输入样例 #1

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

输出样例 #1

Possible

输入样例 #2

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

输出样例 #2

Impossible

输入样例 #3

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

输出样例 #3

Impossible

说明

### 制約 - $ 2\ \leq\ H,\ W\ \leq\ 8 $ - $ a_{i,j} $ は `#` または `.` である。 - 問題文および $ a $ で与えられる情報と整合するような駒の動き方が存在する。 ### Sample Explanation 1 右、下、右、下、右、下、右と駒が動くと、通るマスが与えられた情報と合致します。