题目：Overlapping Squares
思路：dfs打表。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<sstream>
#include<queue>
#include<set>
using namespace std;#define n 6
#define w 5
#define h 9struct Square {bool a[w+5][h+5];Square() {memset(a,0,sizeof(a));}bool operator <(const Square& other) const {for(int i=0; i<w; i++) {for(int j=0; j<h; j++) {if(a[i][j]<other.a[i][j]) return true;if(a[i][j]>other.a[i][j]) return false;}}return false;}
};Square in;
map<Square,int> mp;void Change(Square& x,int row,int col) {x.a[row][2*col+1]=1;x.a[row][2*col+3]=1;x.a[row+1][2*col+1]=0;x.a[row+1][2*col+3]=0;x.a[row+2][2*col+1]=1;x.a[row+2][2*col+3]=1;x.a[row+1][2*col]=1;x.a[row+1][2*col+2]=0;x.a[row+1][2*col+4]=1;x.a[row+2][2*col]=1;x.a[row+2][2*col+2]=0;x.a[row+2][2*col+4]=1;
}void dfs(int step,Square x) {if(step==n) {return ;}for(int i=0; i<=2; i++) {for(int j=0; j<=2; j++) {Square y=x;Change(y,i,j);if(!mp.count(y)||mp[y]>step+1) mp[y]=step+1,dfs(step+1,y);}}
}bool init() {memset(in.a,0,sizeof(in.a));string s;for(int i=0; i<w; i++) {getline(cin,s);if(s[0]=='0') {return false;}for(int j=0; j<h; j++) {if(s[j]=='_') {in.a[i][j]=true;}if(s[j]=='|') {in.a[i][j]=true;}}}
}int main() {Square x;dfs(0,x);int T=0;while(init()) {T++;if(!mp.count(in)) printf("Case %d: No\n",T);else printf("Case %d: Yes\n",T);}return 0;
}