费解的开关

费解的开关

题目传送门： 费解的开关

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式
第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式
一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围
0 输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

解析：
我们分析这道题的话一定要明确以下几点：

每一个位置最多只会 *** 作一次，因为如果 *** 作两次的话，那么就相当于不 *** 作，不满足最优解我们 *** 作的顺序不影响最终的结果当我们确定了第i行的状态时，我们对第i+1行需要进行的 *** 作也就确定了

那么我们的大致思路就是，首先暴力枚举出第一行可能出现的所有情况，因为当我们确定了第一行，那么我们我们对第二行需要进行的 *** 作也就完全确定了，同理，则我们可以确定后面所有行的 *** 作。

代码如下：

#include 
#include 
#include 
#include 

using namespace std;

int cnt; //用cnt表示我们最终的 *** 作数
//用state数组保存我们要对第一行灯做的 *** 作，state[i]=1表示我们要按下i这个位置的灯，用state[i]=2表示不按
int state[10]; 
char g[10][10],backup[10][10]; //用g数组保存灯的的状态，用backup保存着g数组最初的状态

//turn函数为我们按下（x，y）这个位置的灯时所需要的 *** 作
void turn(int x,int y)
{
    int dx[5]={-1,0,0,0,1},dy[5]={0,-1,0,1,0}; //用dx，dy数组保存5个点的改变量
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=5||b<0||b>=5) continue;
        
        if(g[a][b]=='0') g[a][b]='1'; //改变灯的状态
        else g[a][b]='0';
    }
}

void dfs(int u)
{
    if(u==5) //此时已经搜索完第一行，即第一行灯的状态已经确定
    {
        int sum=0; //计数器，保存这种情况时需要的步数
        for(int i=0;i<5;i++)
        {
            if(state[i]==1) //state[i]=1时表示我们要改变i这个位置灯的状态
            {
                sum++;
                turn(0,i);
            }
        }
        
        //当我们确定了第i行灯的状态时，我们也就确定了我们对第i+1行所需要进行的操作
        //因为当第i行第j个位置的灯不亮时，我们肯定要改变第i+1行的第j个位置灯的状态，以使得它亮
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<5;j++)
            {
                if(g[i][j]=='0')
                {
                    sum++;
                    turn(i+1,j);
                }
            }
        }
        
        //判断最后一行的灯是否全亮，如果不是，则肯定不满足要求    
        bool dark=false;
        for(int i=0;i<5;i++)
        {
            if(g[4][i]=='0')
            {
                dark=true;
                break;
            }
        }
            
        if(!dark) cnt=min(cnt,sum); //更新cnt
        memcpy(g,backup,sizeof backup); //把g数组恢复成最初的状态
        
        return;
    }
    
    state[u]=2;
    dfs(u+1);
    
    state[u]=1;
    dfs(u+1);
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        for(int i=0;i<5;i++) cin>>g[i];
        memcpy(backup,g,sizeof g); //复制数组
        
        cnt=10;
        dfs(0); //递归搜索
        
        if(cnt>6) cnt=-1;
        cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710671.html