#P1380. [Baltic2001]Box of Mirrors

[Baltic2001]Box of Mirrors

题目描述

数学家 AndrisAndris 有一个小盒子,其底部是 n×mn\times m 的格子,每个格子可以放一面方向统一为 / 的镜子,也可以不放镜子。

在盒子的边界,每行每列的两端,有一些孔,光线可以从中射入盒子,也可以射出。

如上图所示,从孔 22 射进盒子的光线经过两次反射后又从孔 77 射出。

AndrisAndris 想请你设计一个盒子,使得从每个孔射入的光线都会从指定的孔射出。

例如,如果他希望从 1010 个孔射入的光线分别由孔 9,7,10,8,6,5,2,4,1,39,7,10,8,6,5,2,4,1,3 射出,则上图也是一个满足要求的盒子。

孔从左边界最上端开始依次编号:左边界自上而下 nn 个孔,底边界自左而右 mm 个孔,右边界自下而上 nn 个孔,顶边界自右而左 mm 个孔,共 2(n+m)2(n+m) 个。

输入格式

第一行两个整数 n,mn,m ,表示盒子的大小。

接下来 2×(n+m)2\times(n+m) 行,第 i+1i+1 行一个整数 aia_i 表示从第 ii 个孔射入的光线要从第 aia_i 个孔射出。

输出格式

输出一个 n×mn\times m 的矩阵,对于每个位置,00 表示不放镜子,11 则表示放,需要满足对应的要求。

2 3
9
7
10
8
6
5
2
4
1
3
0 1 0
0 1 1

数据规模与约定

对于 100%100\% 的数据,1≤n,m≤1001\leq n,m\leq 100,1≤ai≤2×(n+m)1\leq a_i\leq2\times(n+m)。

本站当前数据版本保证存在满足全部出入对应关系的镜子布局;允许输出任意一组合法矩阵。