ARC031-B 埋め立て（AtCoder精進記録）

B - 埋め立て

AtCoder Regular Contest 031-B

〇問題
・'x' : 海、'o' : 陸
例：

xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx

で、一か所だけ海を埋め立て（ 'x' -> 'o' ）て陸地をすべて繋げるか。

〇方針
・今回も深さ優先探索
・考え方は以下の通り。

1. 左上から順に、海が見つかるまで探す。海なら埋め立て 。
2. つながっている陸地を数え上げる（深さ優先探索）。
3. （元の陸地の数 ＋ １）まで数えられたら全ての陸地がつながっていると判断。陸地の数が少なければ、埋め立てた海を元に戻し、1．に戻る。

・前回（
ATC079-A 深さ優先探索（Atcoder精進記録） - 胡瓜のプログラミング日記
）のソースコードを流用。

〇ソースコード（C言語）

#include <stdio.h>
#include <stdbool.h>
#define Row 10
#define Column 10

void dfs(int x,int y);
void initialize( bool reached[Row][Column] );

int i,j;
char A[Row][Column];
bool reached[Row][Column];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int flg = 0;
int riku_count=0,srow,scolumn,count=0;

int main(){
    for(i=0;i<Row;i++){
        scanf("%s",A[i]);
    }

    for(i=0;i<Row;i++){
        for(j=0;j<Column;j++){
            if( A[i][j] == 'o' ){
                riku_count++;
                if( flg == 0 ){
                    srow = i;
                    scolumn = j;
                    flg++;
                }
            }       
        }
    }

    if( riku_count == 100 ){
        printf("YES\n");
        return 0;
    }

    for(i=0;i<Row;i++){
        for(j=0;j<Column;j++){
            if( A[i][j] == 'x' ){
                A[i][j] = 'o';
                dfs(srow,scolumn);
                if( count == riku_count + 1 ){
                    printf("YES\n");
                    return 0;
                }
                A[i][j] = 'x';
                count = 0;
                initialize(reached);
            }
        }
    }

    printf("NO\n");

    return 0;
}

void dfs(int x,int y){
    if( x < 0 || Row <= x || y < 0 || Column <= y || A[x][y] == 'x' ){
        return;
    }
    if( reached[x][y] == true ){
        return;
    }
    if( A[x][y] == 'o' ){
        count++;
    }
    
    reached[x][y] = true;

    dfs(x+1, y);
    dfs(x-1, y);
    dfs(x, y+1);
    dfs(x, y-1);
}

void initialize( bool reached[Row][Column] ){
    int a,b;
    for(a=0;a<Row;a++){
        for(b=0;b<Column;b++){
            reached[a][b] = false;
        }
    }
}

〇所感
・深さ優先探索も、単純な奴は大丈夫そう。
・競プロ以外も勉強しているので、そのうち。
・「Atcoder」⇒「AtCoder」に修正。

〇参考記事
・AtCoder 版！蟻本 (初級編)　（問題の選択）