1168: PIPI的方格

题目描述

PIPI有一个N*N的方格，每个格子中有一个数字（0或者1），PIPI可以使任意格子中的0变成1，现在它想让每个格子的上下左右相邻格子中数字之和为偶数。
请你告诉PIPI，最少使用几次操作(将0变成1)，才能使每个格子的上下左右（如果存在）相邻数字和为偶数。

输入

多组数据
第一行为一个正整数n，n<=15
接下来n行，每行n个数字（0或者1）。

输出

对于每组数据，输出一个整数，代表最少需要多少次操作。
若无解，输出-1.

样例输入

3
0 0 0
0 0 0
0 0 0
3
0 0 0
1 0 0
0 0 0
3
1 1 1
1 1 1
0 0 0

样例输出

0
3
-1

思路

此题关键在于确定第一行后，整个方格都会被确定（第 i 行由第 i - 1 行元素确定）。故使用二进制枚举法枚举第一行所有可能的状态，填充方格，判断合法性，统计变换次数即可。

#include<bits/stdc++.h>
using namespace std;
int bef[20][20], aft[20][20], n;
int main()
{
	while(scanf("%d", &n) != EOF)
	{	
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				scanf("%d", &bef[i][j]);
				
		int t = 1 << n, ans = -1;
		
		// 遍历第一行的 2^n - 1 种情况 
		for(int i = 0; i < t; i++)
		{
			for(int j = 1; j <= n; j++)
				for(int k = 1; k <= n; k++)
					aft[j][k] = bef[j][k];

			int cnt = 0;	
			bool flag = true;
			// 获取第一行 
			for(int j = 0; j < n; j++)
			{
				aft[1][n - j] = (i >> j) & 1;
				if(bef[1][n - j] != aft[1][n - j])
				{
					if(bef[1][n - j] == 0)
						cnt++;
					else
					{
						flag = false;
						break;
					}
				}
					
			}
			if(!flag)
				continue;
			// 填充剩下的行 
			for(int j = 1; j < n; j++)
			{
				for(int k = 1; k <= n; k++)
				{
					if((aft[j - 1][k] + aft[j][k - 1] + aft[j][k + 1] + aft[j + 1][k]) & 1 == 1)
					{
						if(aft[j + 1][k] == 0)
						{
							aft[j + 1][k] = 1;
							cnt++;	
						}
						else
						{
							flag = false;
							break;
						}
					}
				}
				if(!flag)
					break;
			}
			if(!flag)
				continue;
			if(ans == -1 || cnt < ans)
				ans = cnt;
		}
		printf("%d\n", ans);
	}
	return 0;
}

二进制枚举

若有 n 个变量，且每个变量只有两种状态则可以考虑使用二进制数来表示这些变量的状态，具体实现的时候采用十进制加位运算来实现。

位运算操作技巧：

A >> X & 1; // A 的第 x 位是否为 1
A & 1; // 可以用来判断 A 是否能被 2 整除，结果为 1 表示不能
1 << x; // 得到 x^2 的值
A ^ (1 << x); //翻转 A 的第 x 位
A << 1; // A * 2
A >> 1; // A / 2
A | (1 << x); // 将 A 的第 x 位置 1
// 注意：如果不熟悉位运算优先级，最好全都打括号。1 << x 可能超出 int 范围但不超出 long long 范围，可以写1ll<<x