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

ゆらのふなびと

競プロ, Python, C++

ゆらふなセンパイお誕生日コンテスト A - 埋め立て

2月14日――世間では「バレンタインデー」と呼ばれ、恋に焦がれる者たちがチョコを渡しあう今日この日――私は22歳の誕生日を迎えながら実家で一人卒論を書いていました。

バレンタインらしいことも誕生日らしいことも特になく、しかも誕生日翌日が卒論提出日というデッドロックの中、なんとか卒論を完成させ打ちひしがれていた私。

そんな私を見かねたのか(?)師匠がこんなものをつくってくれました。

yurahuna2016.contest.atcoder.jp

神か!!!

ということで大喜びで早速解き始めたのでございます。


結果

f:id:pakapa104:20160214233621p:plain

全完!

まあ師匠がちょうどよく選んでくれたので当然と言えば当然なのですが、それでもやっぱり全部解けたのはうれしかったです。決して自分にとっては簡単だったわけではなく、「頑張れば解ける」というレベルだったので。師匠の選問力に脱帽です。

でもかみぺさんに負けた。

f:id:pakapa104:20160214233946p:plain

いや別に根に持ってるわけじゃないですよ?人の誕生日コンテストで1位かっさらっていくなよとかそんなこと全然思ってないですからーやだなーもー

自分にとっては勉強になる問題ばかりだったので、1問ずつ解説を書いていこうと思います(やっとここから本題)


問題

yurahuna2016.contest.atcoder.jp

元問題はこちら

arc031.contest.atcoder.jp

10*10マスの地図が与えられる。'o'は陸地を、'x'は海を表す。'o'が上下左右につながっている領域のことを島と呼ぶ。海を1マスだけ陸地に変えることで島を1つにすることができるか判定せよ。ただし少なくとも1つの陸地, 海があることが保証されている。

解法

とりあえず「埋め立て」と聞いて思い浮かんだのは蟻本にも載っていたこの問題。

2386 -- Lake Counting

この問題では、DFSを使って池を順に塗りつぶしていくことで池の個数をカウントしたのでした。

今回の問題は「ある海のマスを陸地に変えたとき、島が1つになるか」を判定するわけですから、「すべての海のマスについて、それを陸地に変えたときに、そこからDFSしてすべての陸地を塗りつぶせるかを試せばよい」ということになります。

計算量が不安だったのでC++でやったら通りました。

所要時間は20:28

const int N = 10;
char a[N][N+1];
char b[N][N];   //for copy
 
int vx[4] = {1, 0, -1, 0};
int vy[4] = {0, 1, 0, -1};
 
void input() {
    REP(i, N) {
        scanf("%s", a[i]);
    }
}
 
void init_b(int x, int y) {
    REP(i, N) {
        REP(j, N) {
            b[i][j] = a[i][j];
        }
    }
    b[x][y] = 'o';
}
 
bool inside(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}
 
void dfs(int x, int y) {
    if (!inside(x, y)) return;
    if (b[x][y] == 'x') return;
    b[x][y] = 'x';
    REP(k, 4) {
        dfs(x + vx[k], y + vy[k]);
    }
}
 
bool check() {
    REP(i, N) {
        REP(j, N) {
            if (b[i][j] == 'o') {
                return false;
            }
        }
    }
    return true;
}
 
void solve() {
    REP(i, N) {
        REP(j, N) {
            if (a[i][j] == 'x') {
                init_b(i, j);
                dfs(i, j);
                if (check()) {
                    printf("YES\n");
                    return;
                }
            }
        }
    }
 
    printf("NO\n");
}
 
int main() {
    input();
    solve();
    return 0;
}

DFSくらいちゃんと書けないと!と思ってプレッシャーでしたが、1発ACできてよかったです。