AOJ 2091 : Petoris

問題リンク : Petoris | Aizu Online Judge

問題概要：
h * w のピースと H * W のボードがある
ピースとボードは'.'または'#'からなる
'.'はそこが空であることを意味し、'#'はそこが埋まっている亊を意味する
ピースをボード上に置きたい
置く際には、ピースの埋まっている場所とボートの埋まっている場所がかなさらない様にしなければならないし、ピースの埋まっている場所がボードの外にでてはいけない
ピースを置いた際に、ボードの1行すべて埋まったのであればその行数文だけがポイントになる
最大何ポイント得ることができるか？
ピースは回転することができる
ただし、どの場所にもピースを置く亊ができないなら-1と出力せよ

解法：
置ける場所すべてに置いてみる
ピースを置く前に、ピースの形を都合が良いように変更する

....
..#.
.##.
....

上のようなピースが存在した時、それをそのまま置いたのでは
空白の影響でまともに確かめる亊ができない
なので、上下左右の余計な空白をすべて取り除いておく
なので上のピースは以下の様になる

.#
##

あとは全ての場所にピースを０度、９０度、１８０度、２７０度に回転した状態を当てはめてみてポイントを計算する

実装時間:
1時間9分

コード :

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
#include<climits>
#include<cassert>

#define IINF (INT_MAX)
#define MAX 70
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int H,W;
vector<string> G;
vector<string> rot[4];

vector<string> conv(const vector<string>& vec)
{
  int n,e,s,w;
  w = IINF, e = -IINF, n = IINF, s = -IINF;

  for(int y=0;y<vec.size();y++){
    for(int x=0;x<vec[y].size();x++){
      if(vec[y][x] == '.')continue;
      w = min(w,x);
      e = max(e,x);
      n = min(n,y);
      s = max(s,y);
    }
  }

  vector<string> ret;
  for(int y=n;y<=s;y++){
    ret.push_back(vec[y].substr(w,e-w+1));
  }
  return ret;
}


/*
vector<string> conv(const vector<string>& vec)
{
  int n,e,s,w;
  n = w = 0, e = vec[0].size(), s = vec.size();

  //North
  for(int i=0;i<vec.size();i++){
    bool check = true;
    for(int j=0;j<vec[i].size();j++){
      if(vec[i][j] != '.'){
	check = false;
	break;
      }
    }
    if(check){
      n++;
    } else break;
  }

  //South
  for(int i=vec.size()-1;i>=0;i--){
    bool check = true;
    for(int j=0;j<vec[i].size();j++){
      if(vec[i][j] != '.'){
	check = false;
	break;
      }
    }
    if(check){
      s--;
    } else break;
  }

  //West
  for(int x=0;x<vec[0].size();x++){
    bool check = true;
    for(int y=0;y<vec.size();y++){
      if(vec[y][x] != '.'){
	check = false;
	break;
      }
    }
    if(check){
      w++;
    } else break;
  }

  //East
  for(int x=vec[0].size()-1;x>=0;x--){
    bool check = true;
    for(int y=0;y<vec.size();y++){
      if(vec[y][x] != '.'){
	check = false;
	break;
      }
    }
    if(check){
      e--;
    } else break;
  }

  vector<string> ret;
  for(int y=n;y<s;y++){
    ret.push_back(vec[y].substr(w,e-w));
  }
  return ret;
}
*/

vector<string> rotate90(const vector<string>& piece){
  vector<string> ret;
  int h = piece[0].size(), w = piece.size();
  ret.resize(h);
  for(int i=0;i<h;i++)ret[i].resize(w);
  for(int y=0;y<ret.size();y++){
    for(int x=0;x<ret[0].size();x++){
      ret[y][x] = piece[ret[0].size()-1-x][y];
    }
  }
  return ret;
}

void InitPiece(const vector<string>& piece){
  for(int i=0;i<4;i++){
    vector<string> tmp = piece;
    for(int j=0;j<i;j++){
      tmp = rotate90(tmp);
    }
    rot[i] = tmp;
  }
}

int calc(int sx,int sy,int type){
  int ret = 0;
  int h = rot[type].size(), w = rot[type][0].size();
  if(sx+w-1 >= W)return -1;
  if(sy+h-1 >= H)return -1;
  for(int y=sy;y<sy+h;y++){
    bool ok = true;
    for(int x=0;x<W;x++){
      if(sx <= x && x < sx+w){
	if(G[y][x] == '#' && rot[type][y-sy][x-sx] == '#'){
	  return -1;
	}
	else if(G[y][x] == '.' && rot[type][y-sy][x-sx] == '.'){
	  ok = false;
	}
      }else{
	if(G[y][x] != '#'){
	  ok = false;
	}
      }
    }
    if(ok)ret++;
  }
  return ret;
}

void compute(){
  int ans = -1;
  for(int y=0;y<H;y++){
    for(int x=0;x<W;x++){
      for(int type=0;type<4;type++){
	int res = calc(x,y,type);
	ans = max(ans,res);
      }
    }
  }
  cout << ans << endl;
}

int main(){
  int T,h,w;

  cin >> T;
  while(T--){
    cin >> h >> w;

    vector<string> tmp(h);
    for(int i=0;i<h;i++){
      cin >> tmp[i];
    }

    vector<string> piece = conv(tmp);
    InitPiece(piece);

    cin >> H >> W;
    G.resize(H);
    for(int i=0;i<H;i++){
      cin >> G[i];
    }

    compute();

  }
  return 0;
}