Submission #1595094


Source Code Expand

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

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define ll      long long

struct state { int y, x, step; };
static const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void solve() {
        int h, w;
        cin >> h >> w;
        vector<string> s(h);
        int sy, sx, gy, gx;
        for (int y = 0; y < h; y ++) { 
                cin >> s[y];
                for (int x = 0; x < w; x ++) {
                        if (s[y][x] == 's') {
                                sy = y;
                                sx = x;
                        }
                        if (s[y][x] == 'g') {
                                gy = y;
                                gx = x;
                        }
                }
        }
        vector<vector<bool>> used(h, vector<bool>(w, false));
        queue<state> q;
        q.push({sy, sx, 0});
        used[sy][sx] = true;
        bool ans = false;
        while (!q.empty()) {
                state p = q.front(); q.pop();
                if (p.y == gy && p.x == gx) {
                        ans = true;
                        break;
                }
                for (int d = 0; d < 4; d ++) {
                        int xx = p.x + dx[d], yy = p.y + dy[d];
                        if (xx < 0 || xx >= w || yy < 0 || yy >= h) continue;
                        else if (!used[yy][xx] && s[yy][xx] != '#') {
                                used[yy][xx] = true;
                                q.push({yy, xx, p.step + 1});
                        }
                }
        }
        cout << (ans ? "Yes" : "No") << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);

        //int T;
        //freopen("a.in", "r", stdin);
        //cin >> T;
        //while (T --) solve();
        
        solve();
        return 0;
}

Submission Info

Submission Time
Task A - 深さ優先探索
User KokiYmgch
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1989 Byte
Status AC
Exec Time 9 ms
Memory 640 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 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 640 KB
01_rnd_01.txt AC 3 ms 640 KB
01_rnd_02.txt AC 5 ms 640 KB
01_rnd_03.txt AC 6 ms 640 KB
01_rnd_04.txt AC 5 ms 640 KB
01_rnd_05.txt AC 2 ms 640 KB
01_rnd_06.txt AC 8 ms 640 KB
01_rnd_07.txt AC 7 ms 640 KB
01_rnd_08.txt AC 2 ms 640 KB
01_rnd_09.txt AC 2 ms 640 KB
01_rnd_10.txt AC 7 ms 640 KB
01_rnd_11.txt AC 2 ms 640 KB
01_rnd_12.txt AC 8 ms 640 KB
01_rnd_13.txt AC 2 ms 640 KB
01_rnd_14.txt AC 2 ms 640 KB
01_rnd_15.txt AC 6 ms 640 KB
01_rnd_16.txt AC 2 ms 640 KB
01_rnd_17.txt AC 9 ms 640 KB
01_rnd_18.txt AC 2 ms 640 KB
01_rnd_19.txt AC 4 ms 640 KB
02_rndhard_00.txt AC 2 ms 640 KB
02_rndhard_01.txt AC 2 ms 640 KB
02_rndhard_02.txt AC 3 ms 640 KB
02_rndhard_03.txt AC 3 ms 640 KB
02_rndhard_04.txt AC 2 ms 640 KB
02_rndhard_05.txt AC 2 ms 640 KB
02_rndhard_06.txt AC 2 ms 640 KB
02_rndhard_07.txt AC 2 ms 640 KB
02_rndhard_08.txt AC 2 ms 640 KB
02_rndhard_09.txt AC 2 ms 640 KB
02_rndhard_10.txt AC 2 ms 640 KB
02_rndhard_11.txt AC 2 ms 640 KB
02_rndhard_12.txt AC 2 ms 640 KB
02_rndhard_13.txt AC 2 ms 640 KB
02_rndhard_14.txt AC 2 ms 640 KB
02_rndhard_15.txt AC 2 ms 640 KB
02_rndhard_16.txt AC 2 ms 640 KB
02_rndhard_17.txt AC 2 ms 640 KB
02_rndhard_18.txt AC 2 ms 640 KB
02_rndhard_19.txt AC 2 ms 640 KB
02_rndhard_20.txt AC 2 ms 640 KB
02_rndhard_21.txt AC 2 ms 640 KB
02_rndhard_22.txt AC 2 ms 640 KB
02_rndhard_23.txt AC 2 ms 640 KB
02_rndhard_24.txt AC 2 ms 640 KB
02_rndhard_25.txt AC 2 ms 640 KB
02_rndhard_26.txt AC 2 ms 640 KB
02_rndhard_27.txt AC 2 ms 640 KB
02_rndhard_28.txt AC 2 ms 640 KB
02_rndhard_29.txt AC 2 ms 640 KB
02_rndhard_30.txt AC 2 ms 640 KB
02_rndhard_31.txt AC 2 ms 640 KB
02_rndhard_32.txt AC 2 ms 640 KB
02_rndhard_33.txt AC 2 ms 640 KB
02_rndhard_34.txt AC 2 ms 640 KB
02_rndhard_35.txt AC 2 ms 640 KB
02_rndhard_36.txt AC 2 ms 640 KB
02_rndhard_37.txt AC 2 ms 640 KB
02_rndhard_38.txt AC 2 ms 640 KB
02_rndhard_39.txt AC 2 ms 640 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