#P5054. Milk Bottle Data

    ID: 4151 传统题 1000ms 256MiB 尝试: 40 已通过: 2 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索回溯搜索图论二分图建模Kuhn 算法可行性剪枝位运算位集求交模拟与实现技巧增量维护对称性剪枝CF2300

Milk Bottle Data

题目描述

一个被分为n×nn\times n个网格的盒子,每一格有可能包含一瓶牛奶或者什么都没有。史密斯先生对每行从左到右记下牛奶的情况,对每列从上到下记下牛奶的情况。每一条记录包含n个数字,0表示没有牛奶,1表示有牛奶。不幸的是,2n条记录的顺序被打乱了,有些数字也模糊不清。恢复原来盒子的牛奶情况以及原来记录的顺序。

输入格式

从标准输入读入。第一行 nn 表示网格大小

接下来的2n行,每行一条记录,每条记录有n个数字,0表示一定没有牛奶,1表示一定有牛奶,2表示不能确定

其中 1≤n≤101\le n\le 10。

输出格式

第一行输出n个数,第i个数ai表示第ai条记录对应第i行的信息

第二行输出n个数,第i个数bi表示第bi条记录对应第i列的信息

接下来向标准输出写出 nn 行,每行 nn 个连续字符,表示原来盒子的牛奶情况,0表示没有牛奶,1表示有牛奶

上述两行给出的 2n2n 个记录编号必须恰好是 11 到 2n2n 的一个排列,每条记录使用一次。

保证有解,有多组解时输出任意一组即可

样例输入

5 
01210 
21120 
21001 
12110 
12101 
12101 
00011 
22222 
11001 
10010

样例输出

10 9 8 6 2 
4 3 7 5 1 
10010 
11001 
10010 
10101 
01110