Submission #3436552


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/





int H, W, X;
string S[1010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
int ng[1010][1010];
void bfs1() {
    queue<pair<int, int>> que;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '@') {
        que.push({ x,y });
        ng[y][x] = 1;
    }

    rep(_, 0, X) {
        queue<pair<int, int>> que2;
        while (!que.empty()) {
            auto q = que.front(); que.pop();

            int x = q.first;
            int y = q.second;
            rep(i, 0, 4) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (0 <= xx and xx < W and 0 <= y and yy < H) {
                    if (S[yy][xx] == '#') continue;
                    if (!ng[yy][xx]) {
                        que2.push({ xx, yy });
                        ng[yy][xx] = 1;
                    }
                }
            }
        }
        swap(que, que2);
    }
}
//---------------------------------------------------------------------------------------------------
int d[1010][1010];
int bfs2() {
    rep(y, 0, H) rep(x, 0, W) d[y][x] = -1;

    queue<pair<int, int>> que;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == 'S') {
        que.push({ x,y });
        d[y][x] = 0;
    }

    while (!que.empty()) {
        auto q = que.front(); que.pop();

        int x = q.first;
        int y = q.second;

        if (S[y][x] == 'G') return d[y][x];

        rep(i, 0, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (0 <= xx and xx < W and 0 <= y and yy < H) {
                if (S[yy][xx] == '#') continue;
                if (d[yy][xx] < 0 and !ng[yy][xx]) {
                    que.push({ xx, yy });
                    d[yy][xx] = d[y][x] + 1;
                }
            }
        }
    }

    return -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> X;
    rep(y, 0, H) cin >> S[y];

    bfs1();

    /*rep(y, 0, H) {
        rep(x, 0, W) printf("%d ", ng[y][x]);
        printf("\n");
    }*/

    cout << bfs2() << endl;
}

Submission Info

Submission Time
Task C - Ito Campus
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3514 Byte
Status AC
Exec Time 210 ms
Memory 15376 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 30 / 30 370 / 370
Status
AC × 3
AC × 30
AC × 40
Set Name Test Cases
Sample 01_sample_01, 01_sample_02, 01_sample_03
Subtask 01_sample_01, 01_sample_02, 01_sample_03, 02_hand_01, 02_hand_02, 02_hand_03, 02_hand_04, 02_hand_05, 02_hand_06, 02_hand_07, 02_hand_08, 02_hand_09, 02_hand_10, 02_hand_11, 02_hand_12, 02_hand_13, 02_hand_14, 02_hand_15, 02_hand_16, 02_hand_17, 03_rand_01, 03_rand_02, 03_rand_03, 03_rand_04, 03_rand_05, 04_corner_01, 04_corner_02, 04_corner_03, 04_corner_04, 04_corner_05
All 01_sample_01, 01_sample_02, 01_sample_03, 02_hand_01, 02_hand_02, 02_hand_03, 02_hand_04, 02_hand_05, 02_hand_06, 02_hand_07, 02_hand_08, 02_hand_09, 02_hand_10, 02_hand_11, 02_hand_12, 02_hand_13, 02_hand_14, 02_hand_15, 02_hand_16, 02_hand_17, 03_rand_01, 03_rand_02, 03_rand_03, 03_rand_04, 03_rand_05, 04_corner_01, 04_corner_02, 04_corner_03, 04_corner_04, 04_corner_05, 10_rand_01, 10_rand_02, 10_rand_03, 10_rand_04, 10_rand_05, 11_corner_01, 11_corner_02, 11_corner_03, 11_corner_04, 11_corner_05
Case Name Status Exec Time Memory
01_sample_01 AC 2 ms 2304 KB
01_sample_02 AC 2 ms 2304 KB
01_sample_03 AC 2 ms 2304 KB
02_hand_01 AC 2 ms 2304 KB
02_hand_02 AC 2 ms 2304 KB
02_hand_03 AC 2 ms 2304 KB
02_hand_04 AC 2 ms 2304 KB
02_hand_05 AC 2 ms 2432 KB
02_hand_06 AC 2 ms 2432 KB
02_hand_07 AC 153 ms 2304 KB
02_hand_08 AC 171 ms 2304 KB
02_hand_09 AC 2 ms 2304 KB
02_hand_10 AC 2 ms 2304 KB
02_hand_11 AC 2 ms 2304 KB
02_hand_12 AC 2 ms 2304 KB
02_hand_13 AC 2 ms 2304 KB
02_hand_14 AC 1 ms 2304 KB
02_hand_15 AC 153 ms 2304 KB
02_hand_16 AC 2 ms 2304 KB
02_hand_17 AC 2 ms 2304 KB
03_rand_01 AC 2 ms 4608 KB
03_rand_02 AC 2 ms 4608 KB
03_rand_03 AC 2 ms 4608 KB
03_rand_04 AC 2 ms 4608 KB
03_rand_05 AC 2 ms 4608 KB
04_corner_01 AC 2 ms 4608 KB
04_corner_02 AC 2 ms 4608 KB
04_corner_03 AC 2 ms 4608 KB
04_corner_04 AC 3 ms 4608 KB
04_corner_05 AC 2 ms 4608 KB
10_rand_01 AC 31 ms 9160 KB
10_rand_02 AC 33 ms 9344 KB
10_rand_03 AC 30 ms 9036 KB
10_rand_04 AC 20 ms 9328 KB
10_rand_05 AC 32 ms 9016 KB
11_corner_01 AC 51 ms 9376 KB
11_corner_02 AC 50 ms 9324 KB
11_corner_03 AC 50 ms 9324 KB
11_corner_04 AC 210 ms 15376 KB
11_corner_05 AC 47 ms 9372 KB