绍兴商城网站开发设计,网上推广赚钱项目,做的好看的网站,手机网站建设策划题目描述 经过谢老师n次的教导#xff0c;dfc终于觉悟了——过于腐败是不对的。但是dfc自身却无法改变自己#xff0c;于是他找到了你#xff0c;请求你的帮助。 dfc的内心可以看成是5*5个分区组成#xff0c;每个分区都可以决定的的去向#xff0c;0表示继续爱好腐败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)
#includebits/stdc.h
using namespace std;
int a[500001],temp[6][6];
mapint,int b;
int main()
{int n;cinn;int head0,tail1;a[1]33554431;b[33554431]1;while(headtail){head;int tm,tm2;tmtm2a[head];if(b[tm2]-16) continue;for(int i5;i1;i--){for(int j5;j1;j--){temp[i][j]tm%2;tm/2;}}for(int i1;i25;i){int x(i-1)/51;int yi-5*(x-1);int ans0;if(temp[x][y]1) ans-(1(25-i));else ans(1(25-i));if(x15){if(temp[x1][y]1) ans-(1(25-(i5)));else ans(1(25-(i5)));}if(x-11){if(temp[x-1][y]1) ans-(1(25-(i-5)));else ans(1(25-(i-5)));}if(y15){if(temp[x][y1]1) ans-(1(25-(i1)));else ans(1(25-(i1)));}if(y-11){if(temp[x][y-1]1) ans-(1(25-(i-1)));else ans(1(25-(i-1)));}int tm3tm2ans;if(b[tm3]0){b[tm3]b[tm2]1;a[tail]tm3;}}} for(int i1;in;i){string s[6];int x0;for(int j1;j5;j){cins[j];for(int k1;k5;k){x*2;xs[j][k-1]-0;//coutxendl;}}coutb[x]-1endl;}return 0;
}
