最高分数: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} 是
oorx. - 至少有 1 板上有硬币。
子任务/评分
这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。
- (100分):N \leq 8
- (110分):N \leq 16
- (150分):H = 2
- (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
无论他如何命令机器人,他都无法收集所有硬币,同样在这种情况下......