2014年普级组模拟试题一 五香豆腐

2014年普级组模拟试题一 五香豆腐

Description
　经过谢老师n次的教导，dfc终于觉悟了——过于腐败是不对的。但是dfc自身却无法改变自己，于是他到了你，请求你的帮助。
dfc的内心可以看成是5*5个分区组成，每个分区都可以决定的的去向，0表示继续爱好腐败，1表示改正这个不良的习惯。只有当25个分区都为1时，dfc才会改正腐败这个不良习惯。你有一根神奇的魔法棒，可以使点中的分区以及这个分区上下左右改变（1变0,0变1）。这根神奇的魔法棒只能使用6次了，请问你最少使用多少次才可以救醒这dfc。（使用超过6次则输出-1，表示dfc已经无药可救了）。（因为dfc实在太顽固不化，所以你要救醒他n次，但每次都有会获得由谢老师送的一根新的魔法棒,不过之前那根会消失）。
Input
　第一行有一个正整数n，代表数据中共有n组数据。
　　以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了25个分区的初始状态。各组数据间用一个空行分隔。
Output
输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的每组数据最少需要几步才能将救醒dfc。
　　对于一个数据，如果无法在规定的条件救醒dfc，请输出“-1”。
Sample Input

00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
Sample Output

2
-1
Hint
　　0%，n <= 5；
　　100%，n <= 500。

解题思路：
用广搜进行枚举，如果头指针大于6则枚举完，读入方阵后用十进制储存，输出对应答案即可。

varhash:array[0..4000000] of shortint;f,a:array[1..500000] of longint;n,m,l,i,j,k:longint;s:string;function change(x,y:longint):longint;beginx:=x xor (1 shl y);if (y mod 5<>0) then x:=x xor (1 shl (y-1));if ((y1) mod 5<>0) then x:=x xor (1 shl (y1));if (y>4) then x:=x xor (1 shl (y-5));if (y<20) then x:=x xor (1 shl (y5));exit(x);
end;procedure bfs;varhead,tail,i:longint;t,t1:longint;beginhead:=0;tail:=1;f[1]:=1 shl 25-1;hash[f[1]]:=0;a[1]:=0;repeatinc(head);if hash[f[head]]>=6 then break;for i:=0 to 24 dobegint:=change(f[head],i);if hash[t]=-1 thenbeginif hash[f[head]]1<=6 thenbegininc(tail);f[tail]:=t;a[tail]:=head;hash[t]:=hash[f[head]]1;end;end;end;until head>=tail;
end;beginfor i:=0 to 4000000 dohash[i]:=-1;bfs;readln(m);for l:=1 to m dobeginn:=0;for i:=1 to 5 dobeginreadln(s);for j:=1 to 5 dobegink:=ord(s[j])-ord(	0	);n:=n*2k;end;end;writeln(hash[n]);if l<m then readln;end;
end.