読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.360 増加門松No.307 最近色塗る問題多くない?

yukicoder bfs 考察

問題

問題概要

省略

解法

bfsで書いた。やることはシンプルで、色を変えた場所から隣接している同じ色だった部分の色も同時に変わるので、そのようなマスをbfsで探索して色を変えていけばいい。これを実装すると、O(HWQ)となり、TLEしてしまう。ここをどう工夫するかがこの問題の肝。Editorialに書いてあるが、今回の問題は、色が二色しかないので、何回も更新している間に、ほとんど同じ色になるみたい。なぜそうなるのかがよくわからない。
まあ、途中ですべて同じ色になったら、bfsをするのをやめて、最後に何色に変えたかだけを受け取れば、最後0または1ですべてを埋めればよいのかがわかる。

ミス

普通にbfs書いていて、O(HWQ)から抜け出せなかった。難しかった。いい問題でした。

コード

#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};   
int h, w;
int a[210][210];
int q;

int main(void){
    cin >> h >> w;
    rep(i, h)rep(j, w) cin >> a[i][j];

    cin >> q;
    bool flag = false;
    int fcolor;
    rep(i, q){
        int r, c, x; cin >> r >> c >> x;
        r--;c--;
        if(flag){
            fcolor = x;
            continue;
        }
        queue<pair<int, int> > que;
        que.push(make_pair(r, c));
        int color = a[r][c];
        if(color == x) continue;
        a[r][c] = x;
        int cnt = 0;
        while(!que.empty()){
            int nowy = que.front().first, nowx = que.front().second;
            que.pop();
            rep(k, 4){
                int ny = nowy + dy[k], nx = nowx + dx[k];
                if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;
                if(a[ny][nx] == color && a[ny][nx] != x){
                    a[ny][nx] = x;
                    cnt++;
                    que.push(make_pair(ny, nx));
                }
            }
        }
        if(cnt >= h * w - 1){//すべてが同じ色になった
            flag = true;
        }
    }

    if(flag){
        rep(i, h){
            rep(j, w){
                printf("%d ", fcolor);
            }
            printf("\n");
        }
    }else{
        rep(i, h){
            rep(j, w){
                printf("%d ", a[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}