BFS 五香豆腐

题目描述

　　经过谢老师n次的教导，dfc终于觉悟了——过于腐败是不对的。但是dfc自身却无法改变自己，于是他找到了你，请求你的帮助。
dfc的内心可以看成是5*5个分区组成，每个分区都可以决定的的去向，0表示继续爱好腐败，1表示改正这个不良的习惯。只有当25个分区都为1时，dfc才会改正腐败这个不良习惯。你有一根神奇的魔法棒，可以使点中的分区以及这个分区上下左右改变（1变0,0变1）。这根神奇的魔法棒只能使用6次了，请问你最少使用多少次才可以救醒这dfc。（使用超过6次则输出-1，表示dfc已经无药可救了）。（因为dfc实在太顽固不化，所以你要救醒他n次，但每次都有会获得由谢老师送的一根新的魔法棒,不过之前那根会消失）。

　

输入输出格式

输入格式：

　　第一行有一个正整数n，代表数据中共有n组数据。
　　以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了25个分区的初始状态。各组数据间用一个空行分隔。

输出格式：

　　输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的每组数据最少需要几步才能将救醒dfc。
　　对于一个数据，如果无法在规定的条件救醒dfc，请输出“-1”。

输入输出样例

输入样例#1：

输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例#1：

输出样例：
3
2
-1

提示信息

　　30%，n <= 5；
　　100%，n <= 500。

神奇暴力：从目标状态扩展到所有状态，用位运算加速，卡点通过。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int a[500001],temp[6][6];
map<int,int> b;
int main()
{int n;cin>>n;int head=0,tail=1;a[1]=33554431;b[33554431]=1;while(head<tail){head++;int tm,tm2;tm=tm2=a[head];if(b[tm2]-1>=6) continue;for(int i=5;i>=1;i--){for(int j=5;j>=1;j--){temp[i][j]=tm%2;tm/=2;}}for(int i=1;i<=25;i++){int x=(i-1)/5+1;int y=i-5*(x-1);int ans=0;if(temp[x][y]==1) ans-=(1<<(25-i));else ans+=(1<<(25-i));if(x+1<=5){if(temp[x+1][y]==1) ans-=(1<<(25-(i+5)));else ans+=(1<<(25-(i+5)));}if(x-1>=1){if(temp[x-1][y]==1) ans-=(1<<(25-(i-5)));else ans+=(1<<(25-(i-5)));}if(y+1<=5){if(temp[x][y+1]==1) ans-=(1<<(25-(i+1)));else ans+=(1<<(25-(i+1)));}if(y-1>=1){if(temp[x][y-1]==1) ans-=(1<<(25-(i-1)));else ans+=(1<<(25-(i-1)));}int tm3=tm2+ans;if(b[tm3]==0){b[tm3]=b[tm2]+1;a[++tail]=tm3;}}} for(int i=1;i<=n;i++){string s[6];int x=0;for(int j=1;j<=5;j++){cin>>s[j];for(int k=1;k<=5;k++){x*=2;x+=s[j][k-1]-'0';//cout<<x<<endl;}}cout<<b[x]-1<<endl;}return 0;
}