BZOJ 4171 RHL的游戏（高斯消元+压位）

发表于 |
字数统计: 1,147字 | 阅读时长 ≈ 6min

4171: Rhl的游戏

Description

RHL最近迷上一个小游戏：Flip it。游戏的规则很简单，在一个N*M的格子上，有一些格子是黑色，有一些是白色
每选择一个格子按一次，格子以及周围边相邻的格子都会翻转颜色（边相邻指至少与该格子有一条公共边的格子
），黑变白，白变黑。RHL希望把所有格子都变成白色的。不幸的是，有一些格子坏掉了，无法被按下。这时，它
可以完成游戏吗？

Input

第一行一个整数T，表示T组数据。
每组数据开始于三个整数n,m,k，分别表示格子的高度和宽度、坏掉格子的个数。接下来的n行，每行一个长度m的
字符串，表示格子状态为‘B‘或‘W‘。最后k行，每行两个整数Xi,Yi(1≤Xi≤n,1≤Yi≤m)，表示坏掉的格子。
n,m,k<=256,T<=10

Output

对于每组数据，先输出一行Case #i: (1≤i≤T)
如果可以成功，输出YES，否则输出NO。

Sample Input

2
3 3 0
WBW
BBB
WBW
3 3 2
WBW
BBB
WBW
2 2
3 2

Sample Output

Case #1:
YES
Case #2:
NO

如果n,m的范围比较小，那么直接令$X_{i,j}$表示$(i,j)$格子按不按，然后直接高斯消元，不能按的限制等价于一个方程$X_{i,j}=0$

当n,m比较大的时候，直接高斯消元虽然可以利用他比较稀疏的特点优化时间，但空间还是比较卡。
这时考虑缩小变量规模，可以利用$X_{1,i}$表示出$X_{2,i}$进而将$X_{n,i}$表示出来，这样变量规模就缩小到了n的规模。

这依赖于一个等式，对于点$(i,j)$，有$$X_{i-1,j}\oplus X_{i,j}\oplus X_{i,j-1}\oplus X_{i,j+1}\oplus X_{i+1,j}\oplus map[i][j]=0$$
那么利用这个等式，就可以在已知第$i$行和$i-1$行的线性表示的情况下，表示出$i+1$行关于$X_{i,1…m}$的线性表示。
举个例子就是$X_{2,3}=X_{1,3}\oplus X_{1,2}\oplus X_{1,4}\oplus map[1][3]$，这里的$map[1][3]$表示$(1,3)$这个格子是$0\ or\ 1$

那么以此类推到最后一行后，就可以利用$(n,j)$点的等式来列出一个关于$X_{1,1…m}$的方程，总共有m个方程，m个未知数。

对于不能按的限制，由于已知了每个点的线性表示，那么也可以变成一个方程。最后高斯消元即可。

代码实现的时候只需要用一个$bitset$，$F[i][j]$表示$(i,j)$的线性表示中$X_{1,1…m}$的系数，另外用一个$int$数组记录一下$map[i][j]$的异或和即可。

总复杂度$O(Ｔ\frac{n^3}{32})$

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bitset>
#define N 260
using namespace std;
char s[N][N];
bitset<260>map[N],F[N][N],G[N],A,B,C[N];
int T,n,m,k;
bool Gauss(int row,int col)
{
	int i,j,k,MR,x,y;
	for(x=1,y=1,MR=1;x<=row&&y<col;x++,y++,MR=x)
	{
		for(i=x;i<=row;i++)if(C[i][y]==1)MR=i;
		if(C[MR][y]==0){x--;continue;}
		swap(C[x],C[MR]);
		for(i=x+1;i<=row;i++)if(C[i][y])C[i]^=C[x];
	}
	for(i=x;i<=row;i++)if(C[i][col]==1)return 0;
	return 1;
}
int main()
{
	int i,j,tot,x,y,t;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		scanf("%d%d%d",&n,&m,&k);
		memset(C,0,sizeof(C));
		memset(map,0,sizeof(map));
		memset(G,0,sizeof(G));
		memset(F,0,sizeof(F));
		for(i=1;i<=n;i++)scanf("\n%s",&s[i][1]);
		for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)if(s[i][j]=='B')map[i][j]=1;
		for(i=1;i<=m;i++)F[1][i][i]=1;
		for(i=2;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			F[i][j]=F[i-1][j-1]^F[i-1][j]^F[i-1][j+1]^F[i-2][j];
			G[i][j]=G[i-1][j-1]^G[i-1][j]^G[i-1][j+1]^G[i-2][j]^map[i-1][j];
		}
		for(i=1;i<=m;i++)
		{
			C[i]=F[n][i]^F[n][i-1]^F[n][i+1]^F[n-1][i];
			C[i][m+1]=G[n][i]^G[n][i-1]^G[n][i+1]^G[n-1][i]^map[n][i];
		}
		tot=m;
		while(k--)
		{
			scanf("%d%d",&x,&y);
			C[++tot]=F[x][y];
			C[tot][m+1]=G[x][y];
		}
		if(Gauss(tot,m+1))printf("Case #%d:\nYES\n",t);
		else printf("Case #%d:\nNO\n",t);
	}
}