#P18064. Robots
Robots
Robots
有四种机器人,它们在网格中的移动方式如下。坐标 表示第 行、第 列,行号向下增加,列号向右增加。
| 类型 | 允许的移动 |
|---|---|
| A | 向下 或向右 |
| B | 向下 或向左 |
| C | 向上 或向右 |
| D | 向上 或向左 |
网格中的 . 表示空格,# 表示障碍。机器人只能放在空格中,并且只能在网格内的空格之间移动。
给定一棵有 个顶点的树,保证每个非叶顶点的度数至少为 。你需要构造一个 的网格,并放置 个机器人,编号与树的顶点对应。每个机器人的类型可以任意选择,但初始位置必须两两不同。
令 表示第 个机器人能够到达的所有格子的集合,包括它的初始格子。要求对任意两个不同的机器人 :
- 如果树中存在边 ,则 。
- 如果树中不存在边 ,则 。
机器人不阻挡彼此的移动。你只需输出一种满足要求的构造。
输入格式
第一行一个整数 ,表示测试用例数。
每组数据第一行一个整数 ;接下来 行,每行两个整数 ,表示树的一条边。
输出格式
对每组数据:
- 先输出 行,每行 个字符,字符只能是
.或#,表示网格。 - 再输出 行,第 行输出两个整数 和一个字符 ,表示第 个机器人的位置和类型。
所有坐标满足 ,$c_i\in\{\texttt{A},\texttt{B},\texttt{C},\texttt{D}\}$。有多种可行方案时,输出任意一种。
数据范围
,。输入是一棵树,顶点编号为 到 。当 时,每个顶点的度数为 或至少 ; 的单顶点树也合法。
样例
1
5
1 2
1 3
1 4
1 5
......
......
......
.##...
..#...
......
6 1 C
1 6 C
1 5 D
2 6 A
2 5 B