题目链接
这里给出DFS和BFS代码，方便以后回忆。
DFS：
#include <bits/stdc++.h> using namespace std; int G[30][30],d[5]={0,0,1,0,-1},ans; void Rever(int r,int c)//翻转 { for(int i=0;i<5;i++) G[r+d[i]][c+d[(i+1)%5]]^=1; } void resdfs(int r,int c,int cnt)//从第二行翻转，使得上一行全为1 { if(cnt>6) return; else if(r==6) { for(int i=1;i<=5;i++) if(!G[5][i]) return; ans=min(ans,cnt); return; } if(c==6) { resdfs(r+1,1,cnt); return; } if(!G[r-1][c]) { Rever(r,c); resdfs(r,c+1,cnt+1); Rever(r,c); } else resdfs(r,c+1,cnt); } void dfs(int c,int cnt)//枚举第一行所有的翻转可能 { if(c>5) return; Rever(1,c); dfs(c+1,cnt+1); resdfs(2,1,cnt+1); Rever(1,c); dfs(c+1,cnt); resdfs(2,1,cnt); } int main() { int n; cin>>n; while(n--) { for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) scanf("%1d",&G[i][j]); ans=7; dfs(1,0); if(ans>6) ans=-1; cout<<ans<<endl; } return 0; }
BFS:
BFS是从全为1的状态，搜索6步能走到的所有状态。
有一点很奇怪，如果输入为
printf("%d\n",mp[res]==0?-1:mp[res]);
则会超时。
改成
printf("%d\n",mp[res]-1);
便通过了，运行时间在500ms左右。
#include <bits/stdc++.h> using namespace std; map<int,int> mp; int Rever(int x,int n) { x^=1<<n; if(n-1>=0&&n%5) x^=1<<(n-1); if(n+1<25&&n%5!=4) x^=1<<(n+1); if(n-5>=0) x^=1<<(n-5); if(n+5<25) x^=1<<(n+5); return x; } void bfs() { queue<int>que; que.push((1<<25)-1); mp[(1<<25)-1]=1; while(!que.empty()) { int x=que.front(); que.pop(); if(mp[x]>6) return; for(int i=0;i<25;i++) { int rex=Rever(x,i); if(!mp[rex]) { que.push(rex); mp[rex]=mp[x]+1; } } } } int main() { bfs(); int n,x; scanf("%d",&n); while(n--) { int res=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++) { scanf("%1d",&x); res=(res<<1)+x; } printf("%d\n",mp[res]-1); } return 0; }
