QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 1024 MB Points totaux : 100

#5473. 移动一枚硬币

Statistiques

一些硬币被放置在二维平面上的网格点上。没有两枚硬币堆叠在同一个点上。我们将这种硬币的放置方式称为源模式(source pattern)。题目同时给出了另一种相同数量硬币的放置方式,称为目标模式(target pattern)。

源模式与目标模式不匹配,但通过将源模式中的恰好一枚硬币移动到一个空闲的网格点上,所得的新模式将与目标模式匹配。你的任务是找出这样的一次硬币移动。

在此,如果一个模式可以通过对平面进行若干次 90 度旋转,并在必要时进行平行移动(但不进行镜像翻转)得到另一个模式,则称这两个模式匹配。例如,在图 D.1 左侧的源模式中,通过将位于 $(1, 0)$ 的硬币移动到 $(3, 1)$,我们得到了右侧的模式,该模式与图 D.2 所示的目标模式匹配。

图 D.1. 源模式与一次移动

图 D.2. 目标模式

输入格式

输入包含单个测试用例,格式如下:

$h \ w$ $p_{0,0} \dots p_{0,w-1}$ $\vdots$ $p_{h-1,0} \dots p_{h-1,w-1}$ $H \ W$ $P_{0,0} \dots P_{0,W-1}$ $\vdots$ $P_{H-1,0} \dots P_{H-1,W-1}$

第一行包含两个整数 $h$ 和 $w$,均在 $1$ 到 $500$ 之间(含边界)。$h$ 是源模式描述的高度,$w$ 是宽度。接下来的 $h$ 行,每行包含 $w$ 个字符,描述源模式。字符 $p_{y,x}$ 为 'o' 表示在 $(x, y)$ 处放置了一枚硬币,而 'x' 表示该处没有硬币。

随后的行包含整数 $H$ 和 $W$,以及字符 $P_{y,x}$,以相同的方式描述目标模式。

输出格式

如果答案是将位于 $(x_0, y_0)$ 的硬币移动到 $(x_1, y_1)$,请在第一行按顺序打印 $x_0$ 和 $y_0$,中间用空格隔开;并在第二行按顺序打印 $x_1$ 和 $y_1$,中间用空格隔开。

保证至少存在一种满足要求的移动。当存在多种解时,打印其中任意一个即可。

注意,$0 \le x_0 < w$ 且 $0 \le y_0 < h$ 始终成立,但 $x_1$ 和/或 $y_1$ 可能超出这些范围。

样例

样例输入 1

2 3
xox
ooo
4 2
ox
ox
ox
ox

样例输出 1

1 0
3 1

样例输入 2

3 3
xox
oxo
xox
4 4
oxxx
xxox
xoxo
xxxx

样例输出 2

1 2
-1 -1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.