#P9774. [2020年省队模拟]红蓝大作战
[2020年省队模拟]红蓝大作战
红蓝大作战(rbfight)
题目描述
有一个 行、 列的格点棋盘,其中红点和蓝点各有 个,保证左上角为红点、右下角为蓝点。
同色格点之间两两连一条边。请为所有这些边定向,使两种颜色的全部边形成的 个向量之和为 。只需输出一种方案;无解则报告无解。
若边从 指向 ,对应向量为 ;向量按坐标相加。
输入格式
从标准输入读入。第一行两个整数 ;接下来 行,每行一个长度为 、只含 R 和 B 的字符串,分别表示红点和蓝点。
输出格式
无解时输出 。
否则输出两行 字符串,第一行描述红点间的边,第二行描述蓝点间的边。
分别将每种颜色的点按从上到下、同一行从左到右的顺序编号为 到 。按 ,以及每个 对应的 的顺序,依次输出边 的方向: 输出 1, 输出 0。
每行长度均为 。输出量较大,建议使用快速输出。
样例 1 输入
1 2
RR
BB
样例 1 输出
1
0
样例 2 输入
3 1
R
B
R
R
B
B
样例 2 输出
101
101
样例解释
样例 1 的红边从左向右,蓝边从右向左。样例 2 中,每种颜色的三点分别形成有向环。两例的全部向量之和均为 。
数据范围与约定
所有数据满足 。
| 子任务 | 分数 | 额外限制 | 依赖 |
|---|---|---|---|
| 1 | 10 | 无 | |
| 2 | 20 | 1 | |
| 3 | 为奇数 | 无 | |
| 4 | 2 | ||
| 5 | 30 | 无 | 3、4 |
时间限制:1 秒。内存限制:512 MB。