十全十美
测试数据来自 system/1326
背景
Voldemort最近在电子辞典上玩一个小游戏,名字叫十全十美,就是把一个矩阵排列的白色方格按照一定规则(一次可以将十字形的五个方格反色)全部变成黑色方格。其实很多人都玩过啦!不过Voldemort不才,连第一关5*5都过不了。作为一个新世纪的OIer,你能帮帮他吗?
描述
游戏规则:
在一个具有n*m个方块的矩阵中,所有的方块初始状态都为白色。我们的目标是将所有方块变为黑色。变换规则如下:
·每次可以将排列成十字形的5个方格反色:
■■□□□□□□□
■□□■□□□□□ <=这些变换都是合法的
□□■■■□□■□
□□□■□□■■■
·若一个方格已经被变换过一次,再次变换会使它还原:
□□□□□ □□□□□
□□□■□ => □□■■□
□□■■■ □■□□■
□□□■□ □□■■□
给出矩阵的长n和宽m,要求打印前十个方案和总方案数。
格式
输入格式
只有一行:n m
(1<=n<=100,1<=m<=15)
输出格式
方案的表示方法如下:
·每个方案的第一行打印目前是第几个方案;接下来的n行(每行m列),打印方案矩阵,1表示该位置需要反色一次。
·方案与方案之间有一空行;
·输出顺序:“方案值”递增排列。说简单点就是把矩阵第一行反过来看成一个数字,这个数字就是“方案值”。
例如:(n=5)
...
2
1 0 1 1 0
0 1 1 1 0
1 1 1 0 0
1 1 0 1 1
0 0 0 1 1 //方案值:1101
3
0 1 1 0 1
0 1 1 1 0
0 0 1 1 1
1 1 0 1 1
1 1 0 0 0 //方案值:10110
...
最后打印一行总方案数。
注:
·经过旋转、反转的方案属于不同方案;
·若无解,输出'Impossible'(不要单引号)。
·少于十个方案,则打印全部方案。
其它未提及格式以样例为准
样例1
样例输入1
7 5
样例输出1
1
1 0 0 0 0
0 0 1 1 1
0 0 1 0 1
1 0 1 0 1
0 1 1 1 1
1 1 1 0 0
1 1 0 1 0
2
1 1 0 0 0
1 1 0 1 1
0 0 1 1 1
0 1 1 1 0
0 1 1 0 1
0 0 0 0 0
1 0 0 1 0
3
0 0 1 0 0
1 0 0 0 1
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 0 1 0
0 1 1 1 0
4
0 1 1 0 0
0 1 1 0 1
0 0 0 1 0
1 0 1 0 1
0 1 0 0 0
1 0 1 1 0
0 0 1 1 0
5
1 0 0 1 0
0 0 0 0 0
0 1 1 0 1
0 1 1 1 0
0 0 1 1 1
1 1 0 1 1
1 1 0 0 0
6
1 1 0 1 0
1 1 1 0 0
0 1 1 1 1
1 0 1 0 1
0 0 1 0 1
0 0 1 1 1
1 0 0 0 0
7
0 0 1 1 0
1 0 1 1 0
0 1 0 0 0
1 0 1 0 1
0 0 0 1 0
0 1 1 0 1
0 1 1 0 0
8
0 1 1 1 0
0 1 0 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
1 0 0 0 1
0 0 1 0 0
9
0 0 0 0 1
1 1 1 0 0
1 0 1 0 0
1 0 1 0 1
1 1 1 1 0
0 0 1 1 1
0 1 0 1 1
10
0 1 0 0 1
0 0 0 0 0
1 0 1 1 0
0 1 1 1 0
1 1 1 0 0
1 1 0 1 1
0 0 0 1 1
16
限制
各个测试点1s
(最后一个也1s哦,哼哼哼哼……)
提示
数据规模很小哦!
做这道题会很有成就感的,很多答案排列得很有趣,特别是把15*15的答案中1改成■,0改成□,再去掉空格,哇!赏心悦目!
来源
Voldemort 原创