CQOI2014和谐矩阵

发表于
字数统计: 820字 | 阅读时长 ≈ 4min

CQOI2014和谐矩阵

问题描述

我们称一个有0和1组成的矩阵是和谐的，当且仅当每个元素都有偶数个相邻的1。
一个元素相邻的元素包括它本身，以及他上下左右四个元素（如果存在）。
给定矩阵的行数和列数，请计算并输出一个和谐的矩阵。请注意，所有元素为0的矩阵式不允许的。

输入格式

输入一行，包含两个空格分开的整数m,n，分别表示行数和列数。

输出格式

输出包含m行，每行n个空格分隔的整数（0或1），为所求矩阵。测试数据保证有解。

样例输入

4 4

样例输出

官方给出的数据输出：
0 1 0 0
1 1 1 0
0 0 0 1
1 1 0 1
按照字典序应该输出：
0 0 0 1
0 0 1 1
0 1 0 1
1 1 1 0

提示

1<=m,n<=40
注：由于原题是SPJ，本OJ暂时没有开发此功能，所以修改了官方数据。你需要使第一行的字典序最小，第一行相同的第二行字典序最小，以此类推。

没有字典序最小的限制的话，跑完高斯消元就随便输出一个解。

想要字典序最小，贪心地考虑，肯定是想办法把越靠前的元素变成0.根据高斯消元的性质，对于有多解的方程，方程越靠后，自由变元越靠后。所以按照从右下到左上的顺序列方程，字典序枚举自由变元即可。好像可以直接将所有自由变元置为0？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;

int n,m;
int id[45][45],dx[5]={1,-1,0,0,0},dy[5]={0,0,1,-1,0};

int M[1605][1605],R,C,piv[1605],fid[1605],Ans[1605];

bool Find;
void DFS(int cur,int z)
{
	if(Find)return;
	if(cur==0)
	{
		if(!z)return;
		Find=true;
		int i,j,t;
		for(i=R-fid[0];i;i--)
		{
			t=M[i][C];
			for(j=piv[i]+1;j<C;j++)t^=Ans[j]*M[i][j];
			Ans[piv[i]]=t;
		}
		for(i=1;i<=n;i++,putchar('\n'))
		for(j=1;j<=m;j++)printf("%d ",Ans[id[i][j]]);
		return;
	}
	Ans[fid[cur]]=0;
	DFS(cur-1,z);
	Ans[fid[cur]]=1;
	DFS(cur-1,z|1);
}

void Gauss()
{
	int x,y,i,j;
	for(x=1,y=1;x<=R&&y<C;x++,y++)
	{
		if(!M[x][y])
		{
			for(i=x+1;i<=R;i++)if(M[i][y])break;
			for(j=y;j<=C;j++)swap(M[x][j],M[i][j]);
		}
		if(!M[x][y])
		{
			x--;fid[++fid[0]]=y;
			continue;
		}
		piv[x]=y;
		for(i=x+1;i<=R;i++)
		{
			if(!M[i][y])continue;
			for(j=y;j<=C;j++)M[i][j]^=M[x][j];
		}
	}
}

int main()
{
	int i,j,k;
	
	scanf("%d%d",&n,&m);
	R=n*m;C=R+1;
	
	int cnt=0;
	for(i=n;i;i--)
	for(j=m;j;j--)id[i][j]=++cnt;
	
	int x,y,tx,ty;
	for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
	{
		x=i;y=j;
		for(k=0;k<5;k++)
		{
			tx=x+dx[k];ty=y+dy[k];
			if(tx&&ty&&tx<=n&&ty<=m)M[id[tx][ty]][id[x][y]]=1;
		}
	}
	
	Gauss();
	
	DFS(fid[0],0);
}