NKOJ 1987 手机游戏（高斯消元）

发表于 |
字数统计: 933字 | 阅读时长 ≈ 5min

手机游戏

问题描述

有一个有趣的手机游戏，有n*n个正方形的小按钮，有的按钮是黄色，有的按钮是白色。玩家的任务是通过点击按钮，让所有按钮都变成黄色，点按钮的次数越少，得分越高。
但是按钮有个奇怪的特点，当你点击了坐标为(x,y)的按钮后，坐标为(x,y),(x+1,y),(x-1,y),(x,y-1),(x,y+1)的五个按钮会同时改变自身的颜色，是白色的变成黄色，黄色的变成白色。完成游戏最少需要点击多少次按钮呢？请找出答案。

输入格式
输入格式

第一行，一个整数n，表示有n*n个按钮。(1<=n<=40)
接下来是一个由小写字母'y'和字符'w'构成的n*n的矩阵，描述了游戏开始时的情景。'y'表示该按钮式黄色，'w'表示该按钮式白色。

输出格式

如果能够完成游戏，输出一个整数，表示所需最小点击次数。
如果无法完成游戏，输出"inf"

样例输入

样例输入1：
2
yw
ww

样例输入2：

5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出

样例输出1：
1

 样例输出2：
15

此题是高斯消元的模板题，显然将每一个格子当成未知数，按为1，不按为0，然后地图上每一个格子是否需要按作为常数，系数则是两个格子之间能否相互影响。高斯消元求解后的1的个数就是答案。
此题坑点在于，因为可能存在自由变元，所以需要用DFS来枚举自由变元的取值最后取最优值。

关于时间复杂度，由于每个X最多和5个方程有关，所以消去一个X最多只需要4次消元，因此时间复杂度是$4N^2$也就是$4n^4$。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1644
using namespace std;
char map[44][44];
int n,m[N][N],X[N],id[44][44],cnt,ans=1e9,tot,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void dfs(int x,int y)
{
	if(x==0&&y==0)
	{
		int tmp=0;
		for(int i=1;i<=tot;i++)tmp+=X[i];
		if(ans>tmp)ans=tmp;
		return;
	}
	if(x==y)
	{
		X[y]=m[x][tot+1];
		for(int i=x+1;i<=tot;i++)X[y]^=(X[i]&m[x][i]);
		dfs(x-1,y-1);
	}
	else
	{
		X[y]=0;dfs(x,y-1);
		X[y]=1;dfs(x,y-1);
	}
}
int Gauss(int row,int col)
{
	int MR,i,j,k,x,y,temp;
	for(x=1,y=1;x<=row&&y<col;x++,y++)
	{
		MR=x;
		for(i=x+1;i<=row;i++)
		{
			if(m[i][y]>m[MR][y])MR=i;
			if(m[MR][y]==1)break;
		}
		if(MR!=x)for(i=1;i<=col;i++)swap(m[x][i],m[MR][i]);
		if(m[x][y]==0){x--;continue;}
		for(i=x+1;i<=row;i++)
		if(m[i][y]!=0)for(j=y;j<=col;j++)m[i][j]^=m[x][j];
	}
	for(i=x;i<=row;i++)if(m[i][col])return -1;
	dfs(x-1,col-1);
	return 0;
}
int main()
{
	int i,j,k,x,y;
	scanf("%d",&n);tot=n*n;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)id[i][j]=++cnt;
	for(i=1;i<=n;i++)scanf("%s",&map[i][1]);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)if(map[i][j]=='w')m[id[i][j]][tot+1]=1;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{
		m[id[i][j]][id[i][j]]=1;
		for(k=0;k<4;k++)
		{
			x=i+dx[k];y=j+dy[k];
			if(x&&y&&x<=n&&y<=n)m[id[x][y]][id[i][j]]=1;
		}
	}
	x=Gauss(tot,tot+1);
	if(x==-1)puts("inf");
	else cout<<ans;
}