ATC001-A:深さ優先探索

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoderの問題を解きました．

AtCoder Typical Contestなので，解説は詳しく書かれており

深さ優先探索による塗りつぶしを見ればある程度わかると思います．

それでは，以下にソースコードを示します．

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<iostream>

using namespace std;

const int MAX_W = 500;
const int MAX_H = 500;

void search(int x, int y);

int W, H; // 横幅(Width)と縦幅(Height)
char maze[MAX_W][MAX_H]; // 迷路
bool reached[MAX_W][MAX_H] = {false}; // 到達できるかどうか？

int main()
{
    int sX, sY;    // スタート('s')座標
    int gX, gY; // ゴール('g')座標

    scanf("%d %d", &H, &W);
    for (int i = 0; i < H; i++) // 縦幅(Height)
    {
        for (int j = 0; j < W; j++) // 横幅(Wigth)
        {
            cin >> maze[i][j];
            if (maze[i][j] == 's')
            {
                sX = j; sY = i;
            }
            if (maze[i][j] == 'g')
            {
                gX = j; gY = i;
            }
        }
    }

    search(sX, sY);

    if (reached[gY][gX])
        printf("Yes\n");
    else
        printf("No\n");
}

// スタート座標を(x, y)として関数searchを呼び出す
void search(int x, int y)
{
    // 迷路の外側の場合，何もしない
    if (x < 0 || W <= x || y < 0 || H <= y)
        return;

    // 壁(#)の場合，何もしない
    if (maze[y][x] == '#')
        return;

    // 以前に到達したことがある場合，何もしない
    if (reached[y][x])
        return;

    // 到達した
    reached[y][x] = true;

    // 上下左右4方向に対し，探索を行う
    search(x + 1, y); // 右
    search(x - 1, y); // 左 
    search(x, y + 1); // 下
    search(x, y - 1); // 上
}

注意する点があるといえば，配列の設定の仕方です．

今回は2次元配列で格子状の区画を再現しています．

そのとき，縦幅×横幅[y]xで行っています．

解説のままに書くと，だめなので気をつけてください．