Problem1529--PIPI填数字

1529: PIPI填数字

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 81  Solved: 37
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一个n*n的矩阵,其中有些地方已经被填了数字。现在他要在剩余的地方填上数字0或者1,
使得矩阵按行拼接后得到的字符串字典序最大。但是他有个要求,就是得到的矩阵必须是反对称的,
即当i不等于j时,满足a[i][j]不等于a[j][i],你能帮帮他吗?

Input

多组输入。
第一行输入矩阵的大小n(1<=n<=200)。
接下来输入一个只包含-或0或1的n*n的矩阵,
-代表为空,0和1代表已经填了的数。

Output

输出由填完矩阵得到的字典序最大的字符串。
如果填不出符合要求的矩阵,输出impossible。

Sample Input

3
1-0
--0
-1-
2
-0
0-

Sample Output

110010111
impossible

HINT

第一个用例得到的矩阵为 110
                                         010
                                         111

Source/Category

简单