QOJ.ac

QOJ

時間限制: 10 s 記憶體限制: 1024 MB 總分: 29

#6002. 塞维利亚的园丁

统计

你是塞维利亚的园丁,是歌剧中的一个小角色。歌剧的背景是一个矩形的庭院,包含 $R$ 行 $C$ 列的单元格。你被要求在庭院中安装一个树篱迷宫:每个单元格必须包含一个对角线方向的树篱。对于任何单元格,有两种可能的树篱:从左下到右上(用 / 表示)和从左上到右下(用 \ 表示)。每当两个树篱接触时,它们就形成了一堵连续的墙。

庭院周围是一圈宽度为一个单元格的环,四个角缺失。这些外圈单元格中的每一个都是一位朝臣的住所。这些外圈单元格中的朝臣按顺时针方向编号,从顶行最左侧的单元格开始编号为 $1$,到左列最顶端的单元格结束,编号为 $2 \times (R + C)$。例如,对于 $R = 2, C = 2$,外圈的编号如下所示。(注意此时尚未添加任何树篱。)

1 2 8 3 7 4 6 5

在这部不同寻常的歌剧中,爱情是相互且排他的:每位朝臣恰好爱着另一位朝臣,而对方也只爱着他们。每位朝臣都希望能够穿过树篱迷宫到达他或她的爱人身边,而不遇到任何其他朝臣。也就是说,任何一对相爱的朝臣必须通过迷宫中的一条路径连接起来,且该路径与其他所有路径都被树篱墙隔开。迷宫中存在不属于任何朝臣路径的部分是可以的,只要所有爱人对都能连接起来即可。

给定一份谁爱谁的名单,你能否构建出满足条件的树篱迷宫,或者确定这是 IMPOSSIBLE(不可能的)?

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含一行,包含两个整数 $R$ 和 $C$,随后是一行包含从 $1$ 到 $2 \times (R + C)$ 的所有整数的排列。每个整数代表一位朝臣的编号;列表中的第一位和第二位朝臣相爱且必须连接,第三位和第四位朝臣相爱且必须连接,依此类推。

输出格式

对于每个测试用例,输出一行 Case #x:,其中 $x$ 是测试用例编号(从 $1$ 开始)。然后,如果无法满足条件,再输出一行 IMPOSSIBLE。否则,输出 $R$ 行,每行包含 $C$ 个字符,表示满足条件的树篱迷宫,其中每个字符为 /\。你不能将迷宫中的任何单元格留空。如果存在多种可能的迷宫,你可以输出其中任意一个。

数据范围

$1 \le T \le 500$ $1 \le R \times C \le 100$

样例

样例输入 1

4
1 1
1 4 3 2
1 3
1 8 2 7 3 4 5 6
2 2
8 1 4 5 2 3 7 6
1 1
1 3 2 4

样例输出 1

Case #1:
/
Case #2:
//\
Case #3:
//
\/
Case #4:
IMPOSSIBLE

说明

在样例 3 中,以下朝臣对是爱人:$(8, 1), (4, 5), (2, 3), (7, 6)$。以下是样例输出的示意图:

对于样例 3,请注意这也是一个有效的迷宫:

/\
\/

在样例 4 中,庭院仅由一个单元格组成,因此围绕它的朝臣(从顶部开始顺时针读取)分别是 $1, 2, 3$ 和 $4$。在这个单元格中只有两种可能的选择:/\。第一种选择会形成从 $1$ 到 $4$ 以及从 $2$ 到 $3$ 的路径。第二种选择会形成从 $1$ 到 $2$ 以及从 $3$ 到 $4$ 的路径。然而,这两种选择都无法帮助我们陷入爱河的朝臣,因为在这种情况下,$1$ 爱 $3$,$2$ 爱 $4$。所以这种情况是 IMPOSSIBLE,歌剧将充满悲伤的咏叹调!

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.