AcWing 95 费解的开关

目录

• 前言
• 题目链接
• 思路
• 代码

前言

博客咕咕咕了好久了，是时候写一下了

题目链接

AcWing 95 费解的开关

思路

首先可以看出

1.每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然是不满足最优解

2.在一套方案中，操作的顺序无关紧要。

3.如果我们确定了第I行的操作方案的话，那么后面的行数都可以依此递推，下面给出一个详细的解答。

然后再利用状态压缩，就可以了

代码

#include <bits/stdc++.h>

using namespace std;

int n,m,i,j,k,a[7][7],ans1=1e6,b[7][7];

void read() {

	getchar();

	for (i=1; i<=5; i++) {

		for (j=1; j<=5; j++) {

			char ch=getchar();

			b[i][j]=ch-'0';

		}

		getchar();

	}

}

int main() {

	int n;

	cin>>n;

	while(n--) {

		read();

		for (i=0; i<=(1<<5); i++) {

			for (j=1; j<=5; j++) {

				for (k=1; k<=5; k++)

					a[j][k]=b[j][k];

			}

			int ans=0;

			for (j=1; j<=5; j++)

				if (i>>(j-1) & 1) {

					ans++;

					a[1][j-1]^=1,a[1][j+1]^=1,a[1][j]^=1,a[2][j]^=1;

				}

			for (j=1; j<=4; j++)

				for (k=5; k>=1; k--)

					if (!a[j][k]) {

						ans++;

						a[j][k]^=1,a[j+2][k]^=1,a[j+1][k]^=1,a[j+1][k+1]^=1,a[j+1][k-1]^=1;

					}

			bool ok=true;

			for (j=1; j<=5; j++)

				for (k=1; k<=5; k++)

					if (!a[j][k])

						ok=false;

			if (ok)

				ans1=min(ans1,ans);

		}

		if (ans1>6)

			cout<<-1<<'\n';

		else

			cout<<ans1<<'\n';

		ans1=1e10;

	}

	return 0;

}