ICPC国内予選模擬2015 C ブロック落とし
問題
方針
ずらし方を全探索する.書かれているとおりにひたすら実装する.2時間もかかってしまった…
実装
#include <iostream>
#include <cstdio>
#include <cmath>
#include <array>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)
#ifdef DEBUG
#define dump(x) cout << x << " : " << __LINE__ << endl;
#else
#define dump(x)
#endif
#define CR const &
typedef vector<string> vs;
vector<vs> shift(vector<vs> CR b, int dy, int dx){
vector<vs> res = {{"..",".."},{"..",".."}};
rep(z,2){
rep(y,2)rep(x,2){
int yy = y+dy;
int xx = x+dx;
if(yy >= 2 || xx >= 2 || yy < 0 || xx < 0){
if(b[z][y][x] == '#') return {};
} else {
res[z][yy][xx] = b[z][y][x];
}
}
}
return res;
}
int const INF = 1<<28;
// done
bool hit(vs CR a, vs CR b){
rep(i,2)rep(j,2) if(a[i][j] == '#' && b[i][j] == '#') return true;
return false;
}
bool hit(vector<vs> CR a, vector<vs> CR b){
bool res = hit(a[0],b[0]) || hit(a[1],b[1]);
return res;
}
vector<vs> put(vector<vs> CR down, vector<vs> CR up){
int z = down.size()-2;
while(1){
if(z < 0) break;
if(!hit(vector<vs>{down[z],down[z+1]},
vector<vs>{up[0], up[1]})){
z--;
} else {
break;
}
}
z++;
auto res = down;
rep(i,2){
rep(y,2)rep(x,2){
//printf("%d %d %d %d\n", i,z,y,x);
if(res[i+z][y][x] != '#'){
res[i+z][y][x] = up[i][y][x];
}
}
}
return res;
}
int H,N;
vector<vs> tower;
vector<vector<vs>> block;
// done
int erase(vector<vs> CR t){
int res = 0;
rep(i,t.size()){
if(t[i][0] == "##" && t[i][1] == "##"){
res++;
}
}
return res;
}
// done
int solve(vector<vs> t, int k){
if(k == N){
int x = erase(t);
dump(x);
return x;
} else {
int res = -INF;
loop(dy,-2,3)loop(dx,-2,3){
vector<vs> shifted = shift(block[k], dy,dx);
if(shifted.size() == 0) continue; //return -INF;
auto aft = put(t, shifted);
int e = erase(aft);
aft.erase(remove(aft.begin(), aft.end(), vs{"##","##"}), aft.end());
res = max(res,solve(aft,k+1)+e);
}
return res;
}
}
void show(vector<vs> t){
rep(i,min<int>(t.size(),4)){
rep(j,2){
cout << t[i][j] << "\n";
}
cout << endl;
}
}
int main(){
while(cin >> H >> N && H){
tower = vector<vs>(20, {"..",".."});
block = vector<vector<vs>>(N, {{"..",".."},{"..",".."}});
rep(i,H) cin >> tower[i][0] >> tower[i][1];
rep(i,N){
cin >> block[i][0][0] >> block[i][0][1];
cin >> block[i][1][0] >> block[i][1][1];
if(block[i][0][0] == ".." && block[i][0][1] == ".."){
swap(block[i][0], block[i][1]);
}
}
cout << solve(tower,0) << endl;
}
}