QOJ.ac

QOJ

حد الوقت: 2.5 s حد الذاكرة: 256 MB مجموع النقاط: 100

#12578. 魔方矩形

الإحصائيات

一个旨在征服游戏市场的新谜题是魔方与十五数码游戏的结合。棋盘是一个 $H \times W$ 的框架,上面印有从 $1$ 到 $H \cdot W$ 的所有数字。

唯一允许的操作是翻转某一行或某一列。翻转会反转该行(或该列)元素的顺序。下图展示了第三行被翻转后的效果:

给定一个数字排列顺序任意的棋盘,确定一个翻转序列,使得棋盘能够达到完美排序的状态(如果可能的话)。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述:

每个测试用例的描述以一个空行开始。下一行包含两个空格分隔的整数 $W$ 和 $H$ ($1 \le W, H \le 100$),分别表示谜题的宽度和高度。接下来的 $H$ 行,每行包含 $W$ 个空格分隔的整数,表示连续方块上印有的数字。

输出格式

按输入顺序输出每个测试用例的答案。每个测试用例的输出应以单词 POSSIBLEIMPOSSIBLE 开头,具体取决于是否可以解开该谜题。如果存在解,请(在同一行中)首先打印移动次数(可能为 $0$),然后打印移动描述,每个描述由一个字母 RC 组成,指定是翻转行还是列,后面紧跟要翻转的行或列的索引。

只要解法使用的移动次数不超过 $10 \cdot W \cdot H$,任何解法都将被接受。每个测试用例要么在此限制内可解,要么完全不可解。

样例

输入 1

4
3 3
1 2 3
4 5 6
9 8 7
4 2
1 2 3 4
5 6 7 8
4 4
1 2 15 4
8 7 11 5
12 6 10 9
13 14 3 16
3 4
1 2 4
3 5 6
7 8 9
10 11 12

输出 1

POSSIBLE 1 R3
POSSIBLE 0
POSSIBLE 3 R3 C3 R2
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.