A - 深さ優先探索 の解説記事 (再帰関数を使った方法)

今回はこの問題の解説記事です．
https://atcoder.jp/contests/atc001/tasks/dfs_a

回答コード

#include <bits/stdc++.h>
using namespace std;

int h,w;
bool ans = false;
vector<string> maze(500,"");
vector<vector<bool>> reached(500,vector<bool>(500));

void dfs(int x,int y){

    if( ans ) return ;
    reached.at(y).at(x) = true;
    if( maze.at(y).at(x) == 'g' ) {
        ans = true;
        return ;
    }

    if( 0 < y ) if( maze.at(y-1).at(x) != '#' && !reached.at(y-1).at(x) ) dfs(x,y-1);
    if( y+1 < h ) if( maze.at(y+1).at(x) != '#' && !reached.at(y+1).at(x) ) dfs(x,y+1);
    if( 0 < x ) if( maze.at(y).at(x-1) != '#' && !reached.at(y).at(x-1) ) dfs(x-1,y);
    if( x+1 < w ) if( maze.at(y).at(x+1) != '#' && !reached.at(y).at(x+1) ) dfs(x+1,y);
}

int main() {

    int start_x,start_y;

    cin >> h >> w;
    for(int i=0; i<h; i++) {
        cin >> maze.at(i);
        for(int j=0; j<w; j++) {

            if(maze.at(i).at(j) == 's') {
                start_x = j;
                start_y = i;
            }

        }
    }

    dfs(start_x,start_y);

    cout << ( ans ? "Yes":"No" ) << endl;
}

解説

各パート毎に分けて解説を書いていきます．

下記の変数に関しては複数の関数で扱うためグローバル関数で定義します．
引数で渡す方法もあるのですが，それだと関数の呼び出し時に必要な記載量が多くなり面倒です．
グローバル関数とは? ってなっている人がこちらの記事が参考になると思います．

それぞれの関数の役割は

• h : 迷路の縦の長さ
• w : 迷路の横の長さ
• ans : ゴールに辿り着いたか否か
• maze : 迷路のデータ
• reached : 既に到達したかを記録(trueなら通った, falseならまだ通っていない)

#include <bits/stdc++.h>
using namespace std;

//複数関数間で情報を共有したいのでグローバル関数で定義
int h,w;
bool ans = false;
vector<string> maze(500,"");
vector<vector<bool>> reached(500,vector<bool>(500));

次に肝心の以下の再帰関数の中身を解説します．

void dfs(int x,int y){

    if( ans ) return ;
    reached.at(y).at(x) = true;
    if( maze.at(y).at(x) == 'g' ) {
        ans = true;
        return ;
    }

    if( 0 < y ) if( maze.at(y-1).at(x) != '#' && !reached.at(y-1).at(x) ) dfs(x,y-1);
    if( y+1 < h ) if( maze.at(y+1).at(x) != '#' && !reached.at(y+1).at(x) ) dfs(x,y+1);
    if( 0 < x ) if( maze.at(y).at(x-1) != '#' && !reached.at(y).at(x-1) ) dfs(x-1,y);
    if( x+1 < w ) if( maze.at(y).at(x+1) != '#' && !reached.at(y).at(x+1) ) dfs(x+1,y);
}

まず最初のif文です， ここでは既にゴールに辿りついている場合はそれで終了なのでその時点で探索を中止するために早期に return を実行することで探索を中止しています．

    //既にゴールにとだりついている場合は探索を中止
    if( ans ) return ;

ここでの処理では今いるマスに辿り着いたと言うことを reached と言う配列に記録しています．

    reached.at(y).at(x) = true;

ここのif文でゴールに辿りついた場合の処理を記載しています．

    if( maze.at(y).at(x) == 'g' ) {
        ans = true;
        return ;
    }

そして，肝心の再帰している部分の処理ですがifが二つ連続していてややこしいです． 一つ目のif文は 行き先のif文が `maze` 配列の範囲内なのかと言うことを確認しています． そして，二つ目でそこの参照先が 「通行可能」 && 「未到達のマス」 であることを確認しています．

if文を2つに分割していない場合は， maze.at(y-1).at(x) != '#' && !reached.at(y-1).at(x) を実行する際に配列の範囲外を参照してしまいエラーが発生してしまいます．
この二つのif文をクリアした場合は移動すべきますなので探索を続行するように再帰する処理を書いていきます．
これを上下左右４方向分記載します

    if( 0 < y ) if( maze.at(y-1).at(x) != '#' && !reached.at(y-1).at(x) ) dfs(x,y-1); //上へ行く
    if( y+1 < h ) if( maze.at(y+1).at(x) != '#' && !reached.at(y+1).at(x) ) dfs(x,y+1); //下へ行く
    if( 0 < x ) if( maze.at(y).at(x-1) != '#' && !reached.at(y).at(x-1) ) dfs(x-1,y); //左へ行く
    if( x+1 < w ) if( maze.at(y).at(x+1) != '#' && !reached.at(y).at(x+1) ) dfs(x+1,y); //右へ行く

再帰関数はざっとこんな感じです．


main関数は特に説明することはないと思います．
最後に三項演算子使っていますのでもし「三項演算子とは？」ってなっている人はこちらをご覧ください．

int main() {

    int start_x,start_y;

    //入力部
    cin >> h >> w;
    for(int i=0; i<h; i++) {
        cin >> maze.at(i);
        for(int j=0; j<w; j++) {

            // sの入力を検知した場合に開始地点を格納する変数にそれぞれの値を格納する．
            if(maze.at(i).at(j) == 's') {
                start_x = j;
                start_y = i;
            }

        }
    }

    // 最初の引数にスタート地点のx座標,y座標を記録する．
    dfs(start_x,start_y);

    cout << ( ans ? "Yes":"No" ) << endl;
}