AtCoder Typical Contest 001

Submission #10093583

Source codeソースコード

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

#pragma region template

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using str = string;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define reps(i, k, n) for (int i = (k), i##_len = (n); i < i##_len; ++i)
#define rep(i, n) reps(i, 0, n)
#define all(o) (o).begin(), (o).end()
#define sz(a) ((int)(a).size())
#define debug(x) cerr << x << " (L:" << __LINE__ << ")" << '\n';
#define bit(n) (1LL << (n))

const ll MOD = 1000000007;
const string YES = "Yes";
const string NO = "No";

const ll MAX = (ll)0x3f0000003f000000;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1},
          dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
const pii dxy[] = {mp(1, 0), mp(-1, 0), mp(0, -1), mp(0, 1)};

ll mpow(ll a, ll b, ll m) {
    ll ans = 1;
    do {
        if (b & 1) ans = ans * a % m;
        a = a * a % m;
    } while (b >>= 1);  //  b/=2; }while (b!= 0);
    return ans;
}

inline ll mpow(ll a, ll b) {
    return mpow(a, b, MOD);
}

template <class T>
void print(T& x) {
    cout << x << '\n';
}

struct setup_main {
    setup_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(15);
    }
} setup_main_;
inline bool in(string s, string c) {
    return (s.find(c) != string::npos);
}
inline bool in(string s, char c) {
    return (s.find(c) != string::npos);
}

#pragma endregion

struct point {
    int x;
    int y;
};

ll ans = 0;
const char wall = '#';
const char dot = '.';
signed main() {
    point start = {0, 0};
    point goll = {0, 0};
    // init
    int H, W;
    cin >> H >> W;
    vs c(H);
    rep(hi, H) {
        string ns;
        cin >> ns;
        c[hi] = ns;
        if (in(ns, 's')) start = {hi, (int)(ns.find('s'))};
        if (in(ns, 'g')) goll = {hi, (int)(ns.find('g'))};
    }

    // solve;

    deque<point> st = {};
    st.push_back(start);
    bool cangoll = false;

    while (not(st.empty() or cangoll)) {
        point p = st.back();
        c[p.x][p.y] = wall;
        st.pop_back();
        rep(i, 4) {
            int nx = p.x + dx[i];
            int ny = p.y + dy[i];
            char nc;
            if (nx < 0 or H <= nx or ny < 0 or W <= ny) nc = wall;
            else
                nc = c[nx][ny];
            if (nc == 'g') cangoll = true;
            if (nc == dot) {
                st.push_back(point{nx, ny});
                c[nx][ny] = wall;
            }
        }
    }

    if (cangoll == false) cout << "No\n";
    if (cangoll == true) cout << "Yes\n";

    return 0;
}

Submission

Task問題 A - 深さ優先探索
User nameユーザ名 sr_tsubaki
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2719 Byte
File nameファイル名
Exec time実行時間 6 ms
Memory usageメモリ使用量 1280 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01.txt,00_sample_02.txt,00_sample_03.txt,00_sample_04.txt,00_sample_05.txt
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_min_01.txt AC 1 ms 256 KB
00_min_02.txt AC 1 ms 256 KB
00_min_03.txt AC 1 ms 256 KB
00_min_04.txt AC 1 ms 256 KB
00_min_05.txt AC 1 ms 256 KB
00_min_06.txt AC 1 ms 256 KB
00_min_07.txt AC 1 ms 256 KB
00_min_08.txt AC 1 ms 256 KB
00_sample_01.txt AC 1 ms 256 KB
00_sample_02.txt AC 1 ms 256 KB
00_sample_03.txt AC 1 ms 256 KB
00_sample_04.txt AC 1 ms 256 KB
00_sample_05.txt AC 1 ms 256 KB
01_rnd_00.txt AC 2 ms 512 KB
01_rnd_01.txt AC 5 ms 1152 KB
01_rnd_02.txt AC 2 ms 512 KB
01_rnd_03.txt AC 5 ms 1280 KB
01_rnd_04.txt AC 4 ms 1024 KB
01_rnd_05.txt AC 2 ms 512 KB
01_rnd_06.txt AC 4 ms 640 KB
01_rnd_07.txt AC 5 ms 768 KB
01_rnd_08.txt AC 2 ms 512 KB
01_rnd_09.txt AC 2 ms 512 KB
01_rnd_10.txt AC 5 ms 512 KB
01_rnd_11.txt AC 2 ms 512 KB
01_rnd_12.txt AC 5 ms 1024 KB
01_rnd_13.txt AC 5 ms 896 KB
01_rnd_14.txt AC 2 ms 512 KB
01_rnd_15.txt AC 2 ms 512 KB
01_rnd_16.txt AC 2 ms 512 KB
01_rnd_17.txt AC 6 ms 640 KB
01_rnd_18.txt AC 2 ms 512 KB
01_rnd_19.txt AC 2 ms 512 KB
02_rndhard_00.txt AC 2 ms 512 KB
02_rndhard_01.txt AC 2 ms 512 KB
02_rndhard_02.txt AC 3 ms 512 KB
02_rndhard_03.txt AC 2 ms 512 KB
02_rndhard_04.txt AC 2 ms 512 KB
02_rndhard_05.txt AC 2 ms 512 KB
02_rndhard_06.txt AC 2 ms 512 KB
02_rndhard_07.txt AC 2 ms 512 KB
02_rndhard_08.txt AC 2 ms 512 KB
02_rndhard_09.txt AC 2 ms 512 KB
02_rndhard_10.txt AC 2 ms 512 KB
02_rndhard_11.txt AC 2 ms 512 KB
02_rndhard_12.txt AC 2 ms 512 KB
02_rndhard_13.txt AC 2 ms 512 KB
02_rndhard_14.txt AC 2 ms 512 KB
02_rndhard_15.txt AC 2 ms 512 KB
02_rndhard_16.txt AC 2 ms 512 KB
02_rndhard_17.txt AC 2 ms 512 KB
02_rndhard_18.txt AC 2 ms 512 KB
02_rndhard_19.txt AC 2 ms 512 KB
02_rndhard_20.txt AC 2 ms 512 KB
02_rndhard_21.txt AC 2 ms 512 KB
02_rndhard_22.txt AC 2 ms 512 KB
02_rndhard_23.txt AC 2 ms 512 KB
02_rndhard_24.txt AC 2 ms 512 KB
02_rndhard_25.txt AC 2 ms 512 KB
02_rndhard_26.txt AC 2 ms 512 KB
02_rndhard_27.txt AC 2 ms 512 KB
02_rndhard_28.txt AC 2 ms 512 KB
02_rndhard_29.txt AC 2 ms 512 KB
02_rndhard_30.txt AC 2 ms 512 KB
02_rndhard_31.txt AC 2 ms 512 KB
02_rndhard_32.txt AC 2 ms 512 KB
02_rndhard_33.txt AC 2 ms 512 KB
02_rndhard_34.txt AC 2 ms 512 KB
02_rndhard_35.txt AC 2 ms 512 KB
02_rndhard_36.txt AC 2 ms 512 KB
02_rndhard_37.txt AC 2 ms 512 KB
02_rndhard_38.txt AC 2 ms 512 KB
02_rndhard_39.txt AC 2 ms 512 KB
03_rndhardsmall_00.txt AC 1 ms 256 KB
03_rndhardsmall_01.txt AC 1 ms 256 KB
03_rndhardsmall_02.txt AC 1 ms 256 KB
03_rndhardsmall_03.txt AC 1 ms 256 KB
03_rndhardsmall_04.txt AC 1 ms 256 KB
03_rndhardsmall_05.txt AC 1 ms 256 KB
03_rndhardsmall_06.txt AC 1 ms 256 KB
03_rndhardsmall_07.txt AC 1 ms 256 KB
03_rndhardsmall_08.txt AC 1 ms 256 KB
03_rndhardsmall_09.txt AC 1 ms 256 KB