acwing 95

费解的开关

方法一:二进制枚举 + 位运算 + 递推

熄灯问题同方法解决,参考于郭炜老师;

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

//一共五行五列,每一行可以用一个字符来表示,每一行的列数对应该字符的二进制位
//本题中需要找出最少的步数,并且判断是否能在6步之类完成,所以需要判断按0步数少还是按1步数少
char orilight1[5];//存放正常数组
char orilight2[5];//存放相反数组
char lights[5];//过程中改变数组
char result[5];//结果数组(如果题意需要打印结果数组)

int Getbit(char x,int i){//得到第x行的第i位
    return (x >> i) & 1;
}

void Setbit(char &x,int i,int v){//将x行的第i位设置为v(题目中的0,1变换)
    if(v == 1){
        x |= (1 << i);
    }else{
        x &= ~(1 << i);
    }
}

void Filp(char &x,int i){//翻转x行的第i位
    x ^= (1 << i);
}

void outputresult(char result[]){
    for (int i = 0; i < 5;++i){
        for (int j = 0; j < 5;++i){
            cout << Getbit(result[i], j);
        }
        if(i < 4) cout << endl;
    }
}

int ans = 1 << 30;//存贮结果
void solve(char orilights[]){
    ans = 1 << 30;
    int cnt = 0;//统计按下开关的次数
    /*思路 : 想要将所有行全部熄灭,我们可以从第一行开始,枚举第一行的所有状态,
             (因为是第一行我们可以任意改变其状态然后向下推广查看是否能够全部熄灭)
             得到第一行的一个结果状态后,根据第一行的结果翻转周围,和第二行;
             然后最后lights数组里的第一行结果就是第二行的switchs;
             (因为我们要用第二行来熄灭第一行的所有灯(也就是1)),依次类推逐渐得到
             所有答案;
    */
    for (int i = 0; i <= (1 << 5) - 1;i ++){
        cnt = 0;
        memcpy(lights, orilights, sizeof(orilights));
        char switchs = i;//swithchs代表的是第一行的一个答案结果,它的二进制位如果是1则翻转,反之不翻转
        for (int k = 0; k < 5;k ++){
            result[k] = switchs;
            for (int j = 0; j < 5;j ++){
                if(Getbit(switchs, j) == 1){
                    cnt++;
                    Filp(lights[k], j);
                    if(j > 0) Filp(lights[k],j - 1);
                    if(j < 4) Filp(lights[k],j + 1);
                }
            }
            if(k < 4) lights[k + 1] ^= switchs;
            switchs = lights[k];
        }
        if (lights[4] == 0){
        	ans = min(ans ,cnt);	
//        	outputresult(result);
//          break;
        } 
    }
}

int main(){
    int t;cin >> t;
    while(t --){
        for (int i = 0; i < 5;i ++){
            for (int j = 0; j < 5;j ++){
                char c;cin >> c;
                if(c == '0'){
                    Setbit(orilight1[i], j, 0);
                    Setbit(orilight2[i], j, 1);
                }
                else{
	                Setbit(orilight1[i],j,1);
	                Setbit(orilight2[i],j,0);
	            } 
            }
        }

        solve(orilight1);
        solve(orilight2);
//      if(ans==1<<30)   printf("Impossible\n");
//    	else    printf("%d\n",ans);
        if(ans <= 6)   printf("%d\n",ans);
	    else    printf("-1\n");
    }
    return 0;
}

熄灯问题

#include <iostream>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
char orLights[5];
char lights[5];
char result[5];

int GetBit(char c,int i)
{
	return(c >> i) & 1;
}
void SetBit(char & c,int i,int v)
{
	if(v)
	{
		c |= (1 << i);
	}
	else
		c &= ~(1 << i);
}
void FlipBit(char & c,int i)
{
	c ^= (1 << i);
}
void OutputResult(int t,char result[])
{
	cout << "PUZZLE #" << t << endl;
	for(int i = 0;i < 5;++i)
		for(int j = 0;j < 6;++j)
		{
			cout << GetBit(result[i],j);
			if(j < 5)
				cout << " ";
		} 
		cout << endl;
}
int main()
{
	int T;
	cin >> T;
	for(int t = 1;t <= T;++t)
	{
		for(int i = 0;i < 5;++i)
			for(int j = 0;j < 6;++j)
			{
				int s;
				cin >> s;
				SetBit(orLights[i],j,s);
			}
		for(int n = 0;n < 64;++n)
		{
			int switchs = n;
			memcpy(lights,orLights,sizeof(orLights));
			for(int i = 0;i < 5;++i)
			{
				result[i] = switchs;
				for(int j = 0;j < 6;j++)
				{
					if(GetBit(switchs,j))
					{
						if(j > 0)
							FlipBit(lights[i],j - 1);
						FlipBit(lights[i],j);
						if(j < 5)
							FlipBit(lights[i],j + 1);
					}	
				}	
				if(i < 4)
					lights[i + 1] ^= switchs;
				switchs = lights[i];
			}
			if(lights[4] == 0)
				OutputResult(t,result);
			break;
		}
	}
	return 0;
}

方法二: