TVYJ1266：费解的开关

我对状态空间的理解：https://www.cnblogs.com/AKMer/p/9622590.html

题目传送门：http://www.joyoi.cn/problem/tyvj-1266

这道题的状态空间就是经过若干次开关灯之后每盏灯的状态。

然后我们可以一行一行的来开关灯。首先我们得了解两个性质：

1、每一盏灯要么不动它的开关，要么只动一次。(显然)

2、第\(i\)行我们需要按下开关的灯的位置，在第\(i-1\)行必然是关着的。(因为前\(i-1\)行不会再动了，所以我们必须要关这些位置使得前面\(i-1\)行全亮)

所以、我们可以用一个\(5\)位二进制串来枚举第一行的操作，后面就都跟着性质2做就好了。做完最后一排判断是否全亮，如果全亮就更新答案，否则反之。

时间复杂度：\(O(2^n*n^2)\)

空间复杂度：\(O(n^2)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int inf=2e9;

int ans;

char s[6];

int mp[6][6];

int dx[4]={0,1,0,-1};

int dy[4]={1,0,-1,0};

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void change(int x,int y) {

	for(int k=0;k<4;k++) {

		int nx=x+dx[k],ny=y+dy[k];

		if(nx<0||nx>4||ny<0||ny>4)continue;

		mp[nx][ny]^=1;

	}mp[x][y]^=1;

}//开一次开关影响五盏灯

bool check() {

	for(int i=0;i<5;i++)

		for(int j=0;j<5;j++)

			if(!mp[i][j])return 0;

	return 1;

}//判断是否全部亮起

void dfs(int layer,int tot) {

	if(tot>6)return;//步数大于6不要

	if(layer==5) {if(check())ans=min(ans,tot);return;}//更新答案

	int sta=0,sum=tot;

	for(int i=0;i<5;i++)

		if(!mp[layer-1][i])sta|=1<<i,change(layer,i),sum++;//将上一行是0的位置全部按下开关，使得前layer-1行全部都是1，

	dfs(layer+1,sum);

	for(int i=0;i<5;i++)

		if(sta&(1<<i))change(layer,i);//还原现场

}

int main() {

	int T=read();

	while(T--) {

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

			scanf("%s",s);

			for(int j=0;j<5;j++)

				mp[i][j]=s[j]-'0';

		}ans=inf;

		for(int s=0;s<1<<5;s++) {//枚举第一行操作

			int tot=0;

			for(int i=0;i<5;i++)

				if(s&(1<<i))change(0,i),tot++;//按下第一行开关

			dfs(1,tot);

			for(int i=0;i<5;i++)

				if(s&(1<<i))change(0,i);//还原现场

		}

		if(ans==inf)puts("-1");

		else printf("%d\n",ans);

	}

	return 0;

}

巴特西

TVYJ1266：费解的开关

最新文章

热门文章