费解的开关 （BFS+位运算）

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

解题思路：

  逆向搜索，从开关全亮的状态开始搜索，将6步以内的的所有状态记录下来。

  用25位的二进制数来记录5*5的地图。

读入数据，判断步数。

 

#include<bits/stdc++.h>
using namespace std;
short int mapp[1<<25];                       //int 内存超限 short int 不会
int change(int temp,int x)
{
    int t = temp;
    temp^=(1<<x);
    if(x%5!=0) temp^=1<<(x-1);               //判断左右上下边界
    if(x%5!=4) temp^=1<<(x+1);
    if(x/5!=0) temp^=1<<(x-5);
    if(x/5!=4) temp^=1<<(x+5);
    if(mapp[temp]!=-1) return -1;
    mapp[temp] = mapp[t]+1;
    return temp;
}
void bfs()                                    //BFS搜索所有状态
{
    queue<int>que;
    memset(mapp,-1,sizeof(mapp));
    int temp=(1<<25)-1;
    que.push(temp);
    mapp[temp] = 0;
    while(!que.empty()){
        temp = que.front();
        que.pop();
        if(mapp[temp]>=6) continue;
        for(int i=0;i<25;i++){
            int x = change(temp,i);
            if(x==-1) continue;
            que.push(x);
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); //cin cout 加速
    bfs();
    int T;
    cin>>T;
    while(T--){
        int index=0;
        string str;
        for(int i=0;i<5;i++){
            cin>>str;
            for(int j=0;j<5;j++){
                index<<=1;
                index ^= (str[j]-'0');
            }
        }
        cout<<mapp[index]<<endl;
    }
    return 0;
}