[AcWing 116]飞行员兄弟 题解

题目链接：[https://www.acwing.com/problem/content/118/]

题目大意

给定一个由 '-' 和 '+' 组成的 4x4 的矩阵
对点 (i , j) 的一次操作会使得第 i 行和第 j 列的符号全部发生改变 ('-' -> '+','+' -> '-')
求出一个操作方案，使得每个点都为 '-' 且操作的次数最少
若有多种操作方案，则按照优先级整体从上到下，同行从左到右，使得方案的优先级最高

思路

看到这道题，我下意识地认为需要使用递推解决
于是就想了好久，怎样用上一行的状态改变下面
后来发现，这道题只有 16 个可一进行操作的位置，且容易发现，每个位置最多只能被操作一次
所以这道题就转化为了：在 16 个位置中，选出 x(1 <= x <= 16) 个位置
使得对这 x 个位置进行操作后，所有的点对应的符号都变为 '-'，并且这个方案的“优先级”最高

那么，这道题就变得非常简单了，我们可以通过dfs或者2进制枚举每一种方案，判断这种方案的可行性
若可行，按照题目要求更新最佳方案即可
由于本人正在练习位运算，所以采用位运算枚举

code

include cstdio //博客园的抽风特效会把代码吞掉，所以去掉了井号和书名号
include cstring
include algorithm
include utility
using namespace std;
const int n = 4;
typedef pair pa;
char g[5][5],s[5][5];
int lg[1 << 16];
char readchar() {
	char c = getchar();
	while(c != '-'&&c != '+')c = getchar();
	return c;
}
void change(int x,int y) {
	if(g[x][y] == '-')g[x][y] = '+';
	else g[x][y] = '-';
}
pa get(int x) {//把整数x映射为矩阵上点的下标  eg.1 -> (1,1)  4 -> (1,4)  15 -> (4 , 3)
	++ x;//因为在下面的调用中，直接调用了二进制的位数，比正常的位置少了1，所以要+1
	int a = x / n,b = x - n * a;
	if(!b) {
		-- a;
		b = n;
	}
	return make_pair(a + 1 , b);
}
void turn(int x,int y) {
	for(int i = 1;i <= n;++ i) {
		change(x , i);
		change(i , y);
	}
	change(x , y);//这里是重点，因为这个位置会被操作两遍，相当于没操作
        //所以要在循环外面手动再操作一遍
	return ;
}
bool resc() {//判断是否达到目标状态
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			if(g[i][j] == '+')return false;
		}
	}
	return true;
}
int main() {
	for(int i = 1;i <= n;++ i) {
		for(int j = 1;j <= n;++ j) {
			g[i][j] = readchar();
		}
	}       
	int mx = 16,best = (1 << 16) - 1;
	for(int i = 0;i <= (1 << 16) - 1;++ i) {
		int cnt = 0;
		memcpy(s , g , sizeof(g));//保存原数组
		for(int j = 0;(1 << j) <= i;++ j) {
			if(i >> j & 1) {
				++ cnt;//这个方案里操作的个数                             
				pa p = get(j);
				turn(p.first , p.second);
			}                   
		}
		if(resc()) {//达到目标
			if(mx > cnt) {    
				mx = cnt;
				best = i;
			}
			if(mx == cnt) {
				if(i < best) {//借助二进制数的位数特点，直接通过比大小确定优先级
					best = i;
				}
			}
		}
		memcpy(g , s , sizeof(s));//回溯操作 可以不使用memcpy，手动复原
	}
	printf("%d\n",mx);
	for(int i = 0;i <= 15;++ i) {//输出方案
		if(best & (1 << i)) {
			pa p = get(i);      
			printf("%d %d\n",p.first,p.second);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

感谢大家(▽)

相关

标签