AOJ 2091 Petoris

問題概要

あるグリッドにある形のブロックを当てはめることができるか。
できるなら、すべてうまる行の数の最大値をもとめよ。

解法

全探索。
ですが、ブロックの余分な空白をちゃんと詰めないと、
64＾4　*4でなくて
128＾4＊4
になってしまうので注意。

ソース

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

#define REP(i, b, n) for(int i = b; i<(int)n; i++)
#define rep(i, n) REP(i, 0, n)

using namespace std;

const int N = 64;

char t[N][N];
int H, W;


class Block{
public:
  vector<vector<char> > b;
  void turn(){
    vector<vector<char> >  newb;
    rep(j, b[0].size()){
      vector<char> tmp;
      for(int i = b.size()-1; i>= 0; i--){
	tmp.push_back(b[i][j]);
      }
      newb.push_back(tmp);
    }
    b = newb;
  }
};


bool invalid(int y, int x, Block &b){
  rep(i, b.b.size()){
    rep(j, b.b[i].size()){
      if(b.b[i][j] == '.')continue;
      if(y + i < 0 || y +i >= H || x + j < 0 || x+j >= W)return true;
      if(t[y+i][x+j] == '#')return true;
    }
  }
  return false;
}

void put(int y, int x, Block &b){
  rep(i, b.b.size()){
    rep(j, b.b[i].size()){
      if(b.b[i][j] == '.')continue;
      t[y+i][x+j] = b.b[i][j];
    }
  }
}
void erase(int y, int x, Block &b){
  rep(i, b.b.size()){
    rep(j, b.b[i].size()){
      if(b.b[i][j] == '.')continue;
      t[y+i][x+j] = '.';
    }
  }
}
int calc(){
  int ret = 0;
  rep(i, H){
    bool ok = true;
    rep(j, W){
      if(t[i][j] == '.'){
	ok = false;
	break;
      }
    }
    if(ok)ret++;
  }
  return ret;
}

Block b[4];

int main(){
  int T;
  cin >> T;
  rep(tc, T){
    int h, w;
    cin >> h >> w;
    b[0].b = vector<vector<char> >(h, vector<char>(w));
    rep(i, h){
      rep(j, w){
	cin >> b[0].b[i][j];
      }
    }
    rep(i, b[0].b.size()){
      if(b[0].b[i] == vector<char>(b[0].b[i].size(), '.')){
	b[0].b.erase(b[0].b.begin() + i);
	i--;
      }
    }
    
    b[0].turn();
    rep(i, b[0].b.size()){
      if(b[0].b[i] == vector<char>(b[0].b[i].size(), '.')){
	b[0].b.erase(b[0].b.begin() + i);
	i--;
      }
    }
    
    REP(i, 1, 4){
      b[i] = b[i-1];
      b[i].turn();
    }
    cin >> H >> W;
 
    rep(i, H){
      rep(j, W){
	cin >> t[i][j];
      }
    }
    
    int maxi = -1;
    rep(id, 4){
      REP(i, 0, H){
	REP(j, 0, W){
	  if(invalid(i, j, b[id]))continue;
	  put(i, j, b[id]);
	  maxi = max(calc(), maxi);
	  erase(i, j, b[id]);
	}
      }
    }
    cout << maxi << endl;
  }
  return 0;
}