SRM 417 Div1 Medium CubeNets

問題

1x1x1のサイズの立方体の展開図が文字列として与えられる。'#'はそこが1x1のサイズの面であることを表し、'.'は面ではないことを表す。
この展開図は正しい展開図であるとは限らない。そこで文字列が与えられた時、正しい展開図となっているかを返せ。

やりかた

回転と鏡映を考慮しない場合、立方体の展開図は11種類あるのでそれを予めリストアップしておいて、与えられた展開図を回転・鏡映してこの11種類のうちのどれかと一回でも一致したら正しい、という力技をした。

以下ソース。

class CubeNets {
public:
  vector <string> rotate(vector<string> s){
    int N = s.size(), M = s[0].size();
    vector<string> r(M);
    for(int j = 0; j < M; j++)
      for(int i = N - 1; i >= 0; i--)
	r[j] += s[i][j];
    return r;
  }
  vector<string> mirror(vector<string> s){
    for(int i = 0; i < s.size(); i++)
      reverse(ALL(s[i]));
    return s;
  }
  bool coin(vector<string> s, vector<string> t){
    int dH = s.size() - t.size();
    int dW = s[0].size() - t[0].size();
    for(int i = 0; i <= dH; i++){
      for(int j = 0; j <= dW; j++){
	bool match = true;
	for(int y = 0; y < t.size(); y++)
	  for(int x = 0; x < t[0].size(); x++)
	    if(s[i + y][j + x] != t[y][x]) match = false;
	if(match) return true;
      }
    }
    return false;
  }
  string isCubeNet(vector <string> figure) {
    vector<string> nets[11];
    nets[0] = {"#...",
	       "####",
	       "#..."};
    nets[1] = {"#...",
	       "####",
	       ".#.."};
    nets[2] = {"#...",
	       "####",
	       "..#."};
    nets[3] = {"#...",
	       "####",
	       "...#"};
    nets[4] = {".#..",
	       "####",
	       ".#.."};
    nets[5] = {".#..",
	       "####",
	       "..#."};
    nets[6] = {"###..",
	       "..###"};
    nets[7] = {"##..",
	       ".###",
	       ".#.."};
    nets[8] = {"##..",
	       ".###",
	       "..#."};
    nets[9] = {"##..",
	       ".###",
	       "...#"};
    nets[10] = {"##..",
		".##.",
		"..##"};
    
    for(int i = 0; i < 11; i++){
      vector<string> t = figure;
      for(int j = 0; j < 4; j++){
	t = rotate(t);
	if(coin(t, nets[i])) return "YES";
      }
      t = mirror(t);
      for(int j = 0; j < 4; j++){
	t = rotate(t);
	if(coin(t, nets[i])) return "YES";
      }
    }
    return "NO";
  }
};