← 返回题目列表

AtCoder · 1202Contest_b

B. 与 DEGwer

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

分数: 100 点

问题陈述

这是一个交互问题。由于判断程序(交互器)在最坏的情况下需要1秒左右,因此将时间限制设置得更长。

经过10年的旅程,你终于到达了大撒旦DEGwer的城堡。 城堡的入口是一个地牢,这是到达DEGwer无法避开的地方。

地牢是一个网格, H 行和 W 列。 每一个 H \times W 方格是一个房间,并且有一个 门 任意一对相邻房间之间。 此外,还有一个 入口门 在每个房间的左侧最左边一栏,有一个 出口门 位于每个房间的右侧最右侧的一列中。

现在,所有的门都已 未修复。 您想让地牢能够通过反复穿过打开的门从某个打开的入口门到达某个打开的出口门,而 DEGwer 想要阻止您的目标。 为了各自的目标,你和 DEGwer 交替使用以下魔法。

  • 你的魔法:选择任何未固定的门,将其固定为打开(可通过)。
  • DEGwer的魔法:选择任何未固定的门,将其固定为关闭(无法通过)。

给你尺寸 地牢的 (H, W) 以及谁先使用魔法。 当您和 DEGwer 竭尽全力时,确定您的目标是否可以实现。 此外,如果您的目标可以实现,请指出 交互式 一种可能的方法(你的魔法)可以做到这一点。

约束

  • 1 \leq H \leq 20
  • 1 \leq W \leq 20
  • \textrm{move} 是 First or Second,其中 First 表示你先使用魔法,并且 Second 表示DEGwer首先使用魔法。

输入

输入由标准输入按以下格式给出:

H W \textrm{move}

输出

打印 Yes 如果您的目标可以实现并且 No 否则,假设您和 DEGwer 尽力而为。

另外,如果答案是 Yes,打印 交互式 采用以下格式,您对哪些门使用魔法。 (另请参见示例 2。)

t i j
  • t 是 | or -.
  • i 和 j 是整数。
  • If t = {}|,那么 1 \leq i \leq H 和 1 \leq j \leq W + 1,表示选择作为魔法目标的门是 i从上往下数第 j- 水平通过的门(即水平相邻的两个房间之间的门以及所有入口门和出口门)中从左起第一个。
  • If t = {}-,那么 1 \leq i \leq H - 1 和 1 \leq j \leq W,表示选择作为魔法目标的门是 i从上往下数第 j- 垂直穿过的门(即两个垂直相邻房间之间的门)中从左起第一个。

针对您的输出,将返回相同格式的输入。 请注意,如果 \textrm{move} = {}First,那么你应该打印你的输出,然后打印 Yes,如果 \textrm{move} = {}Second,那么您应该在打印后立即收到输入 Yes。 无论哪种情况, 每次打印内容时,以换行符结束并刷新标准输出.

  • t 是其中之一 |, -, a,和 w.
  • If t 是 | or -,那么它代表DEGwer以同样的方式选择的门。
  • If t = {}a,那么 i = j = 0,表示您的互动答案已被确认为正确答案。
  • If t = {}w,那么 i = j = 0,这意味着您的互动答案已被确认为错误答案。
  • 如果您收到以下输入 t = {}a or t = {}w,您的程序必须立即停止。

示例输入 1

1 1 First

示例输出 1

No

在这种情况下,地牢仅由一个房间组成,其左侧有一个独特的入口门,右侧有一个独特的出口门。 为了你的目标,你必须将两扇门固定为打开状态,但即使你先使用魔法也无法做到这一点。 因此,你的目标是无法实现的。


示例输入 2

2 1 First

示例输出 2

Yes
...

在这种情况下,如下图所示,地牢由两个垂直相邻的房间组成,它们之间有一个独特的垂直可通行门,两个房间的左右两侧总共分别有两个入口和出口门。

| |
 -
| |

你先使用魔法,假设你选择了独特的垂直可通门 - 1 1。 然后,无论DEGwer如何选择门,你都可以从剩下的两扇入口门中选择一扇,从剩下的两扇出口门中选择一扇,这样就达到了你的目的,因为两个房间通过你的第一个魔法而连接起来。

以下是交互式输入和输出的示例。

输入    输出  说明
2 1 First 给出一个输入。
Yes 由于您的目标是可以实现的,您可以打印 Yes.
- 1 1 您将其修复为开放的 1从顶部开始并且 1垂直通行门中从左侧开始。
| 1 2 DEGwer 修复为封闭式 1从顶部开始并且 2水平通行门中从左起第 3 个门,即右上出口门。
| 2 2 您将其修复为开放的 2从顶部开始并且 2水平通行门中从左起第 3 个门,即右下出口门。
| 2 1 DEGwer 修复为封闭式 2从顶部开始并且 1水平通行门中从左起第一个,即左下入口门。
| 1 1 您将其修复为开放的 1从顶部开始并且 1水平通行门中从左起第一个,即左上入口门。
a 0 0 此时,已确认从打开的左上入口门可以到达打开的右下出口门,并且您的程序在收到指示的输入后必须立即停止。

示例输入 3

2 1 Second

示例输出 3

No

地牢与上面相同,但你的目标无法实现,因为 DEGwer 首先使用魔法。 例如,如果DEGwer将唯一的垂直通行门(您在样本2中首先选择的门)固定为关闭状态,那么情况就像样本1的两个平行副本一样,即使您首先使用魔法,您的目标也无法实现。