首页 > 其他 > 详细

费解的开关

时间:2020-04-12 13:00:21      阅读:48      评论:0      收藏:0      [点我收藏+]

由题可得:

1.每个等最多点一次

2.当第一行固定,最多由一种结果,每一行的状态,要由下一行转换过来。所以枚举第一行的状态,来计算答案

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

char g[10][10];
int dx[5] = {0,0,0,-1,1};
int dy[5] = {1,-1,0,0,0};
void turn(int x, int y){
    for(int i = 0; i < 5; ++ i)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || b < 0 || a >= 5 || b >= 5)continue;
        g[a][b] ^= 1;
    }
}
int work(){
    int ans = 1e7 ;
    
    char backup[10][10];
    memcpy(backup, g, sizeof g);
    for(int i = 0; i < 1 << 5; ++ i){
        int res = 0;
        for(int j = 0; j < 5; ++ j)
            if(i >> j & 1)
            turn(0,j), res ++;
        
        for(int j = 0; j < 4; ++ j)
            for(int k = 0; k < 5; ++ k)
                if(g[j][k] == 0){
                    turn(j+1, k);
                    res++;
                }
            
        bool flag = 1;
        for(int j = 0; j < 5; ++ j)if(g[4][j] == 0){
            flag = 0;
            break;
        }
        if(flag) ans = min(ans, res);
        memcpy(g,backup,sizeof backup);
    
    }
    if(ans > 6) ans = -1;
    return ans;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        for(int i = 0; i < 5; ++ i) cin >> g[i];
        cout << work() << endl;
    }
    return 0;
}

 

费解的开关

原文:https://www.cnblogs.com/rstz/p/12684556.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!