你玩过“拉灯”游戏吗?25盏灯排成一个5x5的方形。每一个灯都有一个开关,游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯,用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011

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

01111
11101
10111
10000
11011

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

01111
11001
11001
10100
11011

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

输入格式

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

以下若干行数据分为n组,每组数据有5行,每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

对于3 对于10

输出格式

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

对于某一个游戏初始状态,若6步以内无法使所有灯变亮,请输出“-1”。

输入样例:

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例:

3
2
-1

题目分析

枚举第一行所有情况,再根据第一行的状况依次递推到底。

代码实现

#include <iostream>
#include <vector>
#define x first
#define y second
using namespace std;
using PII = pair <int, int>;
const int N = 5, INF = 0x7fffffff;

int t;
vector <vector <bool>> g(N, vector <bool>(N));
PII dir[4] = {{1,0},{0,1},{-1,0},{0,-1}};
void set(vector <vector <bool>>& g, int i, int j) {
    g[i][j] = !g[i][j];
    for(int k = 0; k < 4; ++k) {
        int I = i + dir[k].x, J = j + dir[k].y;
        if(I >= 0 && I < N && J >= 0 && J < N) g[I][J] = !g[I][J];
    }
}
int address(vector <vector <bool>> g, int st) {
    int cnt = 0, p = 0;
    while(st) {
        if(st & 1) set(g, 0, p), ++cnt;
        ++p;
        st >>= 1;
    }
    for(int i = 1; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            if(!g[i - 1][j]) {
                set(g, i, j);
                ++cnt;
                if(cnt > 6) return 7;
            }
        }
    }
    for(int j = 0; j < N; ++j) if(!g[N - 1][j]) return 7;
    return cnt;
}
void solve() {
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j) {
            char key;
            cin >> key;
            g[i][j] = (key - '0');
        }
    int ans = INF;
    for(int st = 0; st < (1 << N); ++st) ans = min(ans, address(g, st));
    cout << (ans <= 6 ? ans : -1) << '\n';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status