ATC079-A 深さ優先探索（Atcoder精進記録）

A - 深さ優先探索

Atcoder Typical Contest 001-A

〇問題
・'#' : 塀、's' : スタート、'g' : ゴール、'.' : 道

s####
....#
#####
#...g

で、スタートからゴールにたどり着けるか出力。

〇方針
・問題の名前通り、深さ優先探索

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

#include <stdio.h>
#include <stdbool.h>
#define Hmax 500
#define Wmax 500

void dfs(int x,int y);

int i,j,H,W;
char c[Hmax][Wmax];
bool reached[Hmax][Wmax];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int flg = 0;

int main(){

    scanf("%d%d",&H,&W);

    for(i=0;i<H;i++){
        scanf("%s",c[i]);
    }

    for(i=0;i<H;i++){
        for(j=0;j<W;j++){
            if( c[i][j] == 's' ){
                dfs(i,j);
            }
        }
    }

    if( flg == 1 ){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}

void dfs(int x,int y){
    int a,b,k;
    if( x < 0 || H <= x || y < 0 || W <= y || c[x][y] == '#' ){
        return;
    }
    if( reached[x][y] == true ){
        return;
    }
    if( c[x][y] == 'g' ){
        flg = 1;
    }
    reached[x][y] = true;
    for(k=0;k<4;k++){
        a = x + dx[k];
        b = y + dy[k];
        dfs(a,b);        
    }
}

〇所感
・深さ優先探索自体は知っていたが、一から実装したことはあまりなかった。やはり知っているのと実装できるのは違う。
・今回は、四方向の探索にfor文を用いたが、変数kをi,jと同様にグローバル変数としてしまい、何度もWA。dfs(x+1,y)のように書くほうが無難かも。
・次回もDFS。

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