TTPC2015 E マス目色ぬり

2015/09/28 (Mon) AtCoder TTPC DFS

問題

日本語

方針

色が変えられたマスの組合わせを全探索する． 色が変えられたマスからいくつか選び，選んだマスが辺上に来るような長方形をつくる． その幅を±2くらい変えて試す．$O(25 \times 2^K)$．

翌日の D 問題と序盤だけ似てたのでひやっとした．

実装

int N,K;
vvi g;
vi is, js;
 
int cnt(int i1, int j1, int i2, int j2){
    int d = 0;
    int di = i2 - i1 + 1;
    int dj = j2 - j1 + 1;
    if((di*dj)%2 == 1){
        if((i1+j1)%2==0) d++; // red;
        else d--; // blue
    }
    rep(ki,K){
        int i = is[ki], j = js[ki];
        if(i1 <= i && i <= i2 && j1 <= j && j <= j2){
            if((i+j)%2==0) d -= 2;
            else d += 2;
        }
    }
    return abs(d);
}
 
int solve(){
    int ans = 0;
    rep(mask, 1<<K){
        if(mask == 0) continue;
        int max_i = -1, min_i = N+10, max_j = -1, min_j = N+10;
        rep(i,K){
            if(mask >> i & 1){
                max_i = max<int>(max_i, is[i]);
                max_j = max<int>(max_j, js[i]);
                min_i = min<int>(min_i, is[i]);
                min_j = min<int>(min_j, js[i]);
            }
        }
        rangei(di1,-2,2){
            rangei(dj1,-2,2){
                rangei(di2,-2,2){
                    rangei(dj2,-1,2){
                        int i1 = min_i+di1;
                        int i2 = max_i+di2;
                        int j1 = min_j+dj1;
                        int j2 = max_j+dj2;
                        if(i1 > i2) continue;
                        if(j1 > j2) continue;
                        if(i1 < 0 || j1 < 0) continue;
                        if(i2 >= N || j2 >= N) continue;
                        ans = max(ans, abs(cnt(i1,j1,i2,j2)));
                    }
                }
            }
        }
    }
    return ans;
}
 
signed main(){
    while(cin >> N >> K){
        g.resize(N);
        is.clear(), js.clear();
        rep(i,N){
            g[i].resize(N);
            rep(j,N){
                g[i][j] = (i+j)%2==0 ? 1 : -1;
            }
        }
        rep(i,K){
            int y,x;
            cin >> y >> x;
            x--, y--;
            g[y][x] *= -1;
            is.pb(y);
            js.pb(x);
        }
        cout << solve() << endl;
    }
}