問題

codeforces.com

問題概要

W * Hの大きさの板チョコがあり、格子に沿って切ろうとしている

(xi1,yi1)から(xi2,yi2)に切り、必ず一つのピースが２つのピースに分かれるように切る

N回切ったときに存在するN + 1個のピースの大きさをソートして出力する

見られた解法

進む方向に切った部分があるのか、無いのかを判定して進む方法

O(WHn)なので十分間に合うけど...

判定めんどい(これが実装力のなさ)ので

2 * 2 の

oo
oo

のような板チョコを

+++++
+o+o+
+++++
+o+o+
+++++

のようにしてやると、

+は辺

oはチョコみたいにできるので、カットがかんたんにできますね(+の対応する部分を通れないようにする)

あとは座標(x,y)の２つの値がどちらも奇数のところがチョコの部分なので、それをカウントすればOKですね

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int W,H;
int N;
vector<vector<int>> fie;
using P = pair<int,int>;

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

int bfs(int sx,int sy){
    int ans = 0;
    queue<P> que;
    que.emplace(sx,sy);
    fie[sx][sy] = 0;
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();

        if((x % 2 == 1) && (y % 2 == 1)) {
            ans++;
        }
        for(int i = 0;i < 4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(!(1 <= nx && nx <= W * 2 - 1)) continue;
            if(!(1 <= ny && ny <= H * 2 - 1)) continue;
            if(!fie[nx][ny]) continue;
            fie[nx][ny] = 0;
            que.emplace(nx,ny);
        }
    }
    return ans;
}

int main(){
    cin >> W >> H >> N;
    fie.resize(W * 2 + 1,vector<int>(H * 2 + 1,1));
    rep(i,0,N - 1){
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 == x2){
            rep(y,y1 * 2,y2 * 2){
                fie[x1 * 2][y] = 0;
            }
        }
        else{
            rep(x,x1 * 2 ,x2 * 2){
                fie[x][y1 * 2] = 0;
            }
        }
    }
    vector<int> ans;
    rep(i,1,2 * W - 1){
        rep(j,1,2 * H - 1) {
            if (fie[i][j]) {
                ans.push_back(bfs(i, j));
            }
        }
    }

    sort(ans.begin(),ans.end());

    for(int i = 0;i < ans.size();i++){
        cout << ans[i] << " \n"[i + 1 == ans.size()];
    }
}

(実はもっとうまくかける(外枠を通れないようにしておけば、範囲の指定なんて要らない))

ICPCのこの問題も同じようにして解いてますねー

Amazing Mazes | Aizu Online Judge

僕のコード

AIZU ONLINE JUDGE: Code Review

Kutimotiの競プロメモ

格子状に座標が分けられてDFS,BFSするとき

問題

問題概要

見られた解法

判定めんどい(これが実装力のなさ)ので