PIPIOJ 1168: PIPI的方格_综合

1168: PIPI的方格

题目描述

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

输入

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

输出

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

样例输入

样例输出

0
3
-1

思路 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;
}

思路 2

回溯法：采用回溯法枚举第一行的状态，对于每一种第一行可能的状态再填充剩余行，回溯过程中有剪枝，效率更高。

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, a[N][N], cnt, ans, b[N][N];
void dfs(int x)
{
    if(x == n + 1){
    // 第一行已经生成，继续填充剩余行for(int i = 1; i < n; i++){
    for(int j = 1; j <= n; j++){
    if((b[i - 1][j] + b[i][j - 1] + b[i][j + 1] + a[i + 1][j]) & 1 == 1){
    if(a[i + 1][j] == 0){
    cnt++;b[i + 1][j] = 1;}else{
    cnt = 0;return;}	}}}ans = min(cnt, ans);cnt = 0;return;}// 剪枝if(a[1][x] != 1)	{
    b[1][x] = 0;dfs(x + 1);}if(a[1][x] == 0)cnt++;b[1][x] = 1;dfs(x + 1);
}
int main()
{
    while(scanf("%d", &n) != EOF){
    for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%d", &a[i][j]);cnt = 0;ans = (n * n * 2);dfs(1);printf("%d\n", ans == (n * n * 2) ? -1 : ans);}return 0; 
}