Note: 本文最初于 2011年01月24日 星期一 20:08 在 hi.baidu.com/lydrainbowcat 发表。
题目：http://www.tyvj.cn/p/1266
解法1：直接进行全局搜索+Hash
看到这个题，大家首先想到的肯定是枚举——每个开关点或者不点，时间复杂度是O(2^25)，3000多万，单纯的一组可以过，但是题目里有多组数据（出题人当然要防止你爆搜啦），所以不能这么裸的搜。
由于只有6步，我们完全可以倒着搜索出有哪些情况可以在6步以内实现全部亮，然后把这些方案Hash一下，以后就可以直接O(1)的使用啦。
★ 解法2：枚举第一行的状态+判定
这是一种较为简洁高效的做法。
我们经过认真的分析可以发现，当第一行的状态确定不再点以后，剩下的行的状态也就确定了——上一行那一列是0，就点0下边那个（因为上边的行已经不能点了），到最后一行后判断看最后一行是不是都亮了，亮了就更新ans。
所以我们只需要枚举第一行的2^5=32种情况，执行上述扫描判定即可。枚举这32种情况，可以使用DFS，也可以使用位运算——枚举0~31，某一位是1/0表示第一行对应列点/不点。
解法3：高斯消元求解xor方程组
一个格子最后亮或不亮，与它上下左右相邻的格子以及它自己是否点击有关。若它所在十字中有奇数次点击，则最终状态与初态相反，否则与初态相同。
由此我们可以将其等效为xor方程，每个格子对应一个变量，取值为0表示不点，取值为1表示点。每个格子以及影响它的格子对应的变量xor起来，应该等于0（与初态相同）或1（与初态不同），即一个xor方程。最后用高斯消元求出该方程的解即可。
解法2参考程序：
type
arr=array[0..6,0..6]of integer;
var
a:arr;
i,j,k,ans,n:longint;
ch:char;
function judge:boolean;
var
i:longint;
begin
judge:=true;
for i:=1 to 5 do if a[5,i]=0 then judge:=false;
end;
procedure dfs2(i,step:longint);
var
j:integer;
begin
if i=6 then
begin
if (judge)and(step<ans) then ans:=step;
exit;
end;
for j:=1 to 5 do
if a[i-1,j]=0 then
begin
inc(step);
a[i-1,j]:=1;
a[i,j]:=1-a[i,j];
a[i+1,j]:=1-a[i+1,j];
a[i,j-1]:=1-a[i,j-1];
a[i,j+1]:=1-a[i,j+1];
end;
dfs2(i+1,step);
end;
procedure dfs1(i,now:longint);
var
re:arr;
begin
re:=a;
dfs2(2,now);
a:=re;
if i=6 then exit;
dfs1(i+1,now);
a[1,i-1]:=1-a[1,i-1]; a[1,i]:=1-a[1,i]; a[1,i+1]:=1-a[1,i+1]; a[2,i]:=1-a[2,i];
dfs1(i+1,now+1);
a[1,i-1]:=1-a[1,i-1]; a[1,i]:=1-a[1,i]; a[1,i+1]:=1-a[1,i+1]; a[2,i]:=1-a[2,i];
end;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to 5 do
begin
for k:=1 to 5 do
begin
read(ch);
a[j,k]:=ord(ch)-ord('0');
end;
readln;
end;
if i<n then readln;
ans:=maxint;
dfs1(1,0);
if ans<=6 then writeln(ans) else writeln(-1);
end;
end.