TYVJ1266 费解的开关

Rhythm- 2018-07-16 原文

题目描述

你玩过“拉灯”游戏吗？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个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。
对于30%的数据，n<=5；
对于100%的数据，n<=500。

输出

输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。

样例输入

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

样例输出

3
2
-1

分析：这题看上去可以bfs暴搜，但是n=500的数据必定超时。我们更换一下思路，如果从灯全亮的状态开始，逆推搜索，即可把所有成立的状态枚举出来。注意，状态存储可以使用map尽可能的节省内存，部分拷贝此题的OJ如果使用 ans[1<<25] 存储状态会MLE（别问我怎么知道）。

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define range(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define rerange(i,a,b) for(int i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
int t,que[1000000][2],front=0,tail=0;
map<int,int*>ans;
void push(int sta,int ste){
    que[tail][0]=sta;
    que[tail][1]=ste;
    ans[sta]=new int(ste);
    tail++;
}
void init(){
    push((1<<25)-1,0);//全亮为0
    while(front<tail){
        int sta=que[front][0],ste=que[front][1];
        if(ste<6)
            range(i,0,24){
                int k=sta;
                k ^= 1<<i;
                if(i%5 != 0)k ^= 1<<(i-1);//左
                if(i%5 != 4)k ^= 1<<(i+1);//右
                if(i/5 != 0)k ^= 1<<(i-5);//上
                if(i/5 != 4)k ^= 1<<(i+5);//下
                if(ans[k]==NULL)push(k,ste+1);
            }
        ++front;
    }
    cin>>t;
}
void solve(){
    while(t--){
        int tmp=0;string in;
        range(i,1,5){
            cin>>in;
            range(j,0,4){
                tmp<<=1;
                tmp|=in[j]-'0';
            }
        }
        cout<<(ans[tmp]!=NULL?*ans[tmp]:-1)<<endl;
    }
}
int main() {
    init();
    solve();
    return 0;
}