Submission #6975254


Source Code Expand

// https://atcoder.jp/contests/atc001/tasks/dfs_a
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define EPS (1e-9)
#define INF (1e9)
#define INFL (1e18)
#define MOD (1000000007)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define BIT(n) (1LL << (n))
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

#define SIZE 510
char disp[SIZE][SIZE];
PII mv[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}

bool dfs(PII pos) {
    disp[pos.first][pos.second] = '@';
    bool ret = false;
    REP(i, 4) {
        char t = disp[pos.first + mv[i].first][pos.second + mv[i].second];
        if (t == '.') {
            ret = dfs({pos.first + mv[i].first, pos.second + mv[i].second});
            if (ret) {
                return true;
            }
        } else if (t == 'g') {
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    Fill(disp, '#');
    PII start, goal;
    REP(i, h) {
        REP(j, w) {
            char t;
            cin >> t;
            disp[i + 1][j + 1] = t;
            if (t == 's') {
                start = {i + 1, j + 1};
            } else if (t == 'g') {
                goal = {i + 1, j + 1};
            }
        }
    }
    bool ret = dfs(start);
    if (ret) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    // REP(i, h) {
    //     REP(j, w) { cout << disp[i + 1][j + 1]; }
    //     cout << endl;
    // }

    return 0;
}

Submission Info

Submission Time
Task A - 深さ優先探索
User yukke714
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1972 Byte
Status AC
Exec Time 8 ms
Memory 5248 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 5
AC × 83
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
Case Name Status Exec Time Memory
00_min_01.txt AC 1 ms 512 KB
00_min_02.txt AC 1 ms 512 KB
00_min_03.txt AC 1 ms 512 KB
00_min_04.txt AC 1 ms 512 KB
00_min_05.txt AC 1 ms 512 KB
00_min_06.txt AC 1 ms 512 KB
00_min_07.txt AC 1 ms 512 KB
00_min_08.txt AC 1 ms 512 KB
00_sample_01.txt AC 1 ms 512 KB
00_sample_02.txt AC 1 ms 512 KB
00_sample_03.txt AC 1 ms 512 KB
00_sample_04.txt AC 1 ms 512 KB
00_sample_05.txt AC 1 ms 512 KB
01_rnd_00.txt AC 4 ms 512 KB
01_rnd_01.txt AC 5 ms 1664 KB
01_rnd_02.txt AC 5 ms 1280 KB
01_rnd_03.txt AC 5 ms 2432 KB
01_rnd_04.txt AC 5 ms 2432 KB
01_rnd_05.txt AC 4 ms 512 KB
01_rnd_06.txt AC 5 ms 1024 KB
01_rnd_07.txt AC 8 ms 2432 KB
01_rnd_08.txt AC 4 ms 512 KB
01_rnd_09.txt AC 4 ms 512 KB
01_rnd_10.txt AC 6 ms 768 KB
01_rnd_11.txt AC 4 ms 512 KB
01_rnd_12.txt AC 4 ms 896 KB
01_rnd_13.txt AC 5 ms 1408 KB
01_rnd_14.txt AC 4 ms 512 KB
01_rnd_15.txt AC 6 ms 1280 KB
01_rnd_16.txt AC 4 ms 512 KB
01_rnd_17.txt AC 7 ms 1024 KB
01_rnd_18.txt AC 4 ms 512 KB
01_rnd_19.txt AC 8 ms 5248 KB
02_rndhard_00.txt AC 4 ms 512 KB
02_rndhard_01.txt AC 4 ms 512 KB
02_rndhard_02.txt AC 4 ms 512 KB
02_rndhard_03.txt AC 4 ms 512 KB
02_rndhard_04.txt AC 4 ms 512 KB
02_rndhard_05.txt AC 4 ms 512 KB
02_rndhard_06.txt AC 4 ms 512 KB
02_rndhard_07.txt AC 4 ms 512 KB
02_rndhard_08.txt AC 4 ms 512 KB
02_rndhard_09.txt AC 4 ms 512 KB
02_rndhard_10.txt AC 4 ms 512 KB
02_rndhard_11.txt AC 4 ms 512 KB
02_rndhard_12.txt AC 4 ms 512 KB
02_rndhard_13.txt AC 4 ms 512 KB
02_rndhard_14.txt AC 4 ms 512 KB
02_rndhard_15.txt AC 4 ms 512 KB
02_rndhard_16.txt AC 4 ms 512 KB
02_rndhard_17.txt AC 4 ms 512 KB
02_rndhard_18.txt AC 4 ms 512 KB
02_rndhard_19.txt AC 4 ms 512 KB
02_rndhard_20.txt AC 4 ms 512 KB
02_rndhard_21.txt AC 4 ms 512 KB
02_rndhard_22.txt AC 4 ms 512 KB
02_rndhard_23.txt AC 4 ms 512 KB
02_rndhard_24.txt AC 4 ms 512 KB
02_rndhard_25.txt AC 4 ms 512 KB
02_rndhard_26.txt AC 4 ms 512 KB
02_rndhard_27.txt AC 4 ms 512 KB
02_rndhard_28.txt AC 4 ms 512 KB
02_rndhard_29.txt AC 4 ms 512 KB
02_rndhard_30.txt AC 4 ms 512 KB
02_rndhard_31.txt AC 4 ms 512 KB
02_rndhard_32.txt AC 4 ms 512 KB
02_rndhard_33.txt AC 4 ms 512 KB
02_rndhard_34.txt AC 4 ms 512 KB
02_rndhard_35.txt AC 4 ms 512 KB
02_rndhard_36.txt AC 4 ms 512 KB
02_rndhard_37.txt AC 4 ms 512 KB
02_rndhard_38.txt AC 4 ms 512 KB
02_rndhard_39.txt AC 4 ms 512 KB
03_rndhardsmall_00.txt AC 1 ms 512 KB
03_rndhardsmall_01.txt AC 1 ms 512 KB
03_rndhardsmall_02.txt AC 1 ms 512 KB
03_rndhardsmall_03.txt AC 1 ms 512 KB
03_rndhardsmall_04.txt AC 1 ms 512 KB
03_rndhardsmall_05.txt AC 1 ms 512 KB
03_rndhardsmall_06.txt AC 3 ms 512 KB
03_rndhardsmall_07.txt AC 1 ms 512 KB
03_rndhardsmall_08.txt AC 1 ms 512 KB
03_rndhardsmall_09.txt AC 1 ms 512 KB