Submission #1143895

---

Source Code Expand

#include <bits/stdc++.h>

//#define DEBUG


using namespace std;

using ll = long long;
using pii = pair<char,char>;

const int H = 50;
const int W = 50;
const int K = 8;
const int INF = 1 << 29;

const double TIME_LIMIT = 9; // 実行制限時間
struct TimeWatch{
    clock_t start_,end_;
    void start(){start_=clock();}
    double stop(){return (double)(clock()-start_)/CLOCKS_PER_SEC;}
} tw;


bool is_time_limit(){
    return (tw.stop() >= TIME_LIMIT);
}

int gety(pii p){
    return p.first;
}
int getx(pii p){
    return p.second;
}

ll make_rand(){
    static ll x=123456789;
    static ll y=362436069;
    static ll z=521288629;
    static ll w=88675123;
    ll t;
    t=x^(x<<11);
    x=y;y=z;z=w;
    return w=(w^(w>>19))^(t^(t>>8));
}


const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};

ll field[51][51];
int occupy[51][51];


vector<pii> neibhor(int cy, int cx, int H, int W){
    vector<pii> res;
    for(int i = 0; i < 4; i++){
        const int ny = cy + dy[i];
        const int nx = cx + dx[i];
        // if(ny>=0&&nx>=0&&ny<H&&nx<W){
        res.push_back(pii(ny,nx));
        // }
    }
    return res;
}


void print_occupy(){
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            printf("%3d ", occupy[i][j]);
        }
        puts("");
    }
}

bool is_settable(vector<pii> &st, int occupy[51][51]){
    
    for(pii p : st){
        int y = gety(p);
        int x = getx(p);
        if(occupy[y][x] != -1) return false;
    }

    return true;
}

set<pii> reg(set<pii> s){
    int minx = INF, miny = INF;
    for(pii p : s){
        const int y = gety(p);
        const int x = getx(p);
        minx = min(minx, x);
        miny = min(miny, y);
    }
    set<pii> res;
    for(auto it = s.begin(); it != s.end(); it++){
        res.insert(pii(it->first - miny, it->second - minx));
    }
    return res;
}

void solve1(){

    
    vector<vector<pii> > mino;
    // 8x8の領域で, mappingを行う
    {
        int sy = 0, sx = 0;
        queue<set<pii> > q;
        set<set<pii> > used;
        set<pii> init = {pii(sy, sx)};
        used.insert(init);
        q.push(init);
        set<set<pii> > result;
        while(q.size()){
            set<pii> s = q.front(); q.pop();
            if(s.size() == K){
                result.insert(s);
                continue;
            }
            for(pii p : s){
                int cy = gety(p);
                int cx = getx(p);
                for(pii np : neibhor(cy, cx, H, W)){
                    if(!s.count(np)){
                        set<pii> ns = s;
                        ns.insert(np);
                        // nsを正規化する
                        ns = reg(ns);
                        if(!used.count(ns)){
                            used.insert(ns);
                            q.push(ns);
                        }
                    }
                }
            }
        }
        // cout << result.size() << endl;
        for(set<pii> sp : result){
            mino.push_back(vector<pii>(sp.begin(), sp.end()));
            // bool a[10][10] = {};
            // for(auto p : sp){
            //     a[(int)p.first][(int)p.second] = true;
            // }
            // if(!a[0][0]){
            //     for(int i = 0; i < 8; i++){
            //         for(int j = 0; j < 8; j++){
            //             if(a[i][j])cout<<'#';
            //             else cout<<".";
            //         }
            //         cout << endl;
            //     }
            //     cout << endl;
            // }
        }
    }

    vector<pair<ll, vector<pii> > > cands;
    // minx, minyをi,jにあわせたときの, 設置座標とコストを計算する
    for(int i = 0; i < (int)mino.size(); i++){
        const auto &ps = mino[i];
        for(int oy = 0; oy < H; oy++){
            for(int ox = 0; ox < W; ox++){
                ll r = 1;
                vector<pii> v;
                for(const pii &p : ps){
                    int y = gety(p) + oy;
                    int x = getx(p) + ox;
                    v.push_back(pii(y,x));
                    if(y >= 0 && x >= 0 && y < H && x < W){
                        r *= field[y][x];
                    }
                    else{
                        r = 0;
                    }
                }
                if(r){
                    cands.push_back(make_pair(r, v));
                }
            }
        }
    }

#ifdef DEBUG
    cout << cands.size() << endl;
#endif

    // biggest order
    sort(cands.begin(), cands.end(), 
         [](const pair<ll, vector<pii> > &p1, const pair<ll, vector<pii> > &p2){
             return p1.first > p2.first;
         });


    memset(occupy, -1, sizeof(occupy));

    vector<bool> used(cands.size(), false);
    // 評価値の高い順番にgreedyに設置する
    for(int idx = 0; idx < (int)cands.size(); idx++){
        // 設置可能か調べる
        if(is_settable(cands[idx].second, occupy)){
            used[idx] = true;
            for(pii p : cands[idx].second){
                occupy[gety(p)][getx(p)] = idx;
            }
        }
    }

    // // 時間いっぱいまで適当に山登りでスコアが上がる場所を探す
    // // tieの場合はswapしたい
    // while(!is_time_limit()){
    //     // usedな要素を一つランダムに選び, 元に戻す

    //     // unusedな要素のうち、設置可能になった要素を探す
    //     // 最もスコアが上がる要素で置き換える
        
    // }
    


// #ifdef DEBUG
//     cout << "total peace : " << peaces.size() << endl;
//     // print_occupy();
// #endif


#ifndef DEBUG
    cout << std::count(used.begin(), used.end(), true) << endl;
    for(int idx = 0; idx < (int)cands.size(); idx++){
        if(used[idx]){
            for(pii p : cands[idx].second){
                cout << gety(p) + 1 << " " << getx(p) + 1 << endl;
            }
        }
    }

#endif

}



int main(){
    
    tw.start(); // 時間計測開始
    {
        int h,w,k;
        cin >> h >> w >> k;
    }
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            char ch;
            cin >> ch;
            field[i][j] = ch - '0';
        }
    }
    solve1();
    

    return 0;
}

Submission Info

Judge Result