ICPC国内予選模擬2015 C ブロック落とし

2015/06/20 (Sat) ICPC 全探索 実装

問題

問題文

方針

ずらし方を全探索する.書かれているとおりにひたすら実装する.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;
    }
}