← 返回题目列表

AtCoder · s8pc_6_e

E. 90 度旋转

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

最高分数:800 点

问题陈述

有一块矩形板,上面有 H \times W 细胞。细胞为 i第行和 j第列表示为 (i, j).

某些单元格中有硬币。如果 S_{i, j} = o,里面有一枚硬币 (i, j)。否则,如果 S_{i, j} = x,里面没有金币 (i, j).

E869120会将机器人放入带有硬币的单元格中,他将设置初始方向,选择上/下/左/右。然后,机器人会重复以下动作。

  • 收集机器人牢房中的硬币。然后,旋转 90 向左或向右度。之后,跳到任何有至少进步的硬币的单元格 1 机器人面向方向的单元格。

E869120 的目标是收集棋盘上的所有硬币。当E869120能够决定机器人的初始单元/方向,以及每个动作的旋转方向和跳跃目的地时,确定是否有办法实现目标。

约束

  • 2 \leq H \leq 100
  • 2 \leq W \leq 100
  • S_{i, j} 是 o or x.
  • 至少有 1 板上有硬币。

子任务/评分

这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。

  1. (100分):N \leq 8
  2. (110分):N \leq 16
  3. (150分):H = 2
  4. (440分):没有额外的限制。

当我们让 N 棋盘上的硬币数量。


输入

输入将从标准输入给出,格式如下。

H W
S_{1, 1}S_{1, 2}S_{1, 3}...S_{1, W}
S_{2, 1}S_{2, 2}S_{2, 3}...S_{2, W}
  :   :   :
S_{H, 1}S_{H, 2}S_{H, 3}...S_{H, W}

输出

打印 Possible 是否有办法收集所有硬币;否则,打印 Impossible.


示例输入 1

5 5
xooxx
xoxxo
xxoox
ooxoo
xoxxx

示例输出 1

Possible

他可以通过如下图所示的移动来实现目标。


示例输入 2

2 9
oxxxxoxxo
oxoxxoxxo

示例输出 2

Possible

他可以通过如下图所示的移动来实现目标。


示例输入 3

9 25
xxxxxxxxxxxxxxxxxxxxxxxxx
xxoooxxxoooxxooooxxxoooxx
xoxxxoxoxxxoxoxxxoxoxxxox
xoxxxxxoxxxoxoxxxoxoxxxxx
xxoooxxxoooxxooooxxoxxxxx
xxxxxoxoxxxoxoxxxxxoxxxxx
xoxxxoxoxxxoxoxxxxxoxxxox
xxoooxxxoooxxoxxxxxxoooxx
xxxxxxxxxxxxxxxxxxxxxxxxx

示例输出 3

Impossible

无论他如何命令机器人,他都无法收集所有硬币。


示例输入 4

6 6
oxxxxo
xoooxx
xoooox
xoooox
xxooxx
oxxxxo

示例输出 4

Impossible

无论他如何命令机器人,他都无法收集所有硬币,同样在这种情况下......