洛谷1391 方阵安排

发表于

原题地址

题目描述

A班希望在学校的行军比赛中取得一个好成绩，他们希望自己班级的行军方阵是一个完美的方阵。他们认为，如果每个人四周的男生个数为偶数，那么这就是一个完美的方阵。现在你已知道A班现有的方阵，你需要把尽量少的女生改成男生，使这个方阵变成一个完美的方阵。

输入输出格式

输入格式：

第1行，一个正整数n，表示方阵大小为n*n的。

第2~n+1行，每行n个数，代表方阵中的人（0为女生，1为男生）。

输出格式：

一个数，表示最少需要把女生改成男生的个数。若无解，输出-1；

输入输出样例

输入样例#1：

1
2
3
4
3
0 0 0
1 0 0
0 0 0

输出样例#1：

1
3

说明

对样例的说明：

将方阵改为：0 1 0

1 0 1 0 1 0 即可。

数据范围：

对于40%的数据，n≤6

对于100%的数据，n≤18

思路

对于每一种情况，先枚举第一行的状态(选或不选)

然后将问题转化

转化为已知第一行填之后的n-1行

对于不符合的(将男生化为女生)，终止操作

时间复杂度O(2^n*n^2) 可以接受

上代码

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
#include <cstdio>
#include <algorithm>
using namespace std;
int n,ans=0x7fffffff;
int a[20][20],b[20][20];
int dfs(int st){
	int cnt=0;
	for(int i=0;i<n;++i)
	for(int j=0;j<n;++j)
	b[i][j]=0;
	for(int i=0;i<n;++i){
		if(st&(1<<i))b[0][i]=1;
		else if(a[0][i]==1)return 0x7fffffff;
	}
	for(int i=1;i<n;++i){
		for(int j=0;j<n;++j){
			int tmp=0;
			if(i>1)tmp+=b[i-2][j];
			if(j>0)tmp+=b[i-1][j-1];
			if(j<n-1)tmp+=b[i-1][j+1];
			b[i][j]=tmp%2;
			if(a[i][j]==1&&b[i][j]==0)return 0x7fffffff;
		}
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(a[i][j]!=b[i][j])++cnt;
		}
	}
	return cnt;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	for(int j=0;j<n;++j)
	scanf("%d",&a[i][j]);
	for(int i=0;i<=(1<<n)-1;++i)
	ans=min(ans,dfs(i));
	if(ans==0x7fffffff)puts("-1");
	else printf("%d",ans);
	return 0;
}