Submission #2945125

Source Code Expand

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


int N,M,K;
string d;
vector<string> mp;
vector<vector<int>> ds(4);

ll nearest(ll t, int dir) {
    int r = (int)(t % K);
    if (ds[dir].empty()) return -1;
    int nxt = -1;
    auto a = lower_bound(ALL(ds[dir]), r);
    if (a == ds[dir].end()) {
        nxt = K + ds[dir][0];
    } else {
        nxt = *a;
    }
#ifdef DEBUG
    fprintf(stderr, "nearest (%lld=%d, %d) = %d\n", t,r, dir,nxt );
#endif
    return (t - r) + nxt + 1;
}

ll solve() {
    rep(i,K) {
        switch (d[i]) {
            case 'R': ds[0].pb(i); break;
            case 'U': ds[1].pb(i); break;
            case 'L': ds[2].pb(i); break;
            case 'D': ds[3].pb(i); break;
        }
    }

    vector<ll> dist(N*M, LLONG_MAX);
    vector<int> road(N*M, 0);
    int start, goal;

    rep(r,N) rep(c,M) {
        int loc = r*M + c;
        switch (mp[r][c]) {
            case '#': continue;
            case 'S': start = loc; break;
            case 'G': goal = loc; break;
            case '.': break;
        }
        if (c<M-1) {
            if (mp[r][c+1] != '#') road[loc] |= 1; // R
        }
        if (0<r) {
            if (mp[r-1][c] != '#') road[loc] |= 2; // U
        }
        if (0<c) {
            if (mp[r][c-1] != '#') road[loc] |= 4; // L
        }
        if (r<N-1) {
            if (mp[r+1][c] != '#') road[loc] |= 8; // D
        }
    }
    // dist[start] = 0;

    priority_queue<pair<ll,int>> pq;  // (-dist, loc)
    pq.push(cons(0, start));

    while (!pq.empty()) {
        auto a = pq.top(); pq.pop();
        int loc = a.second, newloc;
        ll t = -a.first, newt;
#ifdef DEBUG
        fprintf(stderr, "now loc=%d, t=%lld\n", loc,t);
#endif
        if (loc == goal) return t;
        if (dist[loc] != LLONG_MAX) continue;
        dist[loc] = t;

        if (road[loc] & 1) { // R
            newloc = loc + 1;
            newt = nearest(t, 0);
            if (newt >= 0) {
                pq.push(cons(-newt, newloc));
            }
        }
        if (road[loc] & 2) { // U
            newloc = loc - M;
            newt = nearest(t, 1);
            if (newt >= 0) {
                pq.push(cons(-newt, newloc));
            }
        }
        if (road[loc] & 4) { // L
            newloc = loc - 1;
            newt = nearest(t, 2);
            if (newt >= 0) {
                pq.push(cons(-newt, newloc));
            }
        }
        if (road[loc] & 8) { // D
            newloc = loc + M;
            newt = nearest(t, 3);
            if (newt >= 0) {
                pq.push(cons(-newt, newloc));
            }
        }
    }
    return -1;
}

int main() {
    // int N,M,K
    cin >> N >> M >> K;
    // string d;
    cin >> d;
    // vector<string> mp(N);
    mp.resize(N);
    rep(i,N) cin >> mp[i];
    cout << solve() << endl;
    return 0;
}

Submission Info

Submission Time
Task E - 迷路
User naoya_t
Language C++14 (GCC 5.4.1)
Score 500
Code Size 4116 Byte
Status
Exec Time 332 ms
Memory 14080 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 292 ms 14080 KB
07.txt 240 ms 13824 KB
08.txt 273 ms 14080 KB
09.txt 251 ms 13824 KB
10.txt 236 ms 13824 KB
11.txt 240 ms 13728 KB
12.txt 332 ms 13724 KB
13.txt 285 ms 13724 KB
14.txt 326 ms 13984 KB
15.txt 284 ms 13732 KB
16.txt 64 ms 13596 KB
17.txt 161 ms 13724 KB
18.txt 144 ms 13980 KB
19.txt 97 ms 13728 KB
20.txt 230 ms 13724 KB
21.txt 302 ms 13692 KB
22.txt 300 ms 13692 KB
23.txt 314 ms 13692 KB
24.txt 304 ms 13692 KB
25.txt 309 ms 13692 KB
26.txt 303 ms 13692 KB
27.txt 307 ms 13692 KB
28.txt 301 ms 13692 KB
29.txt 306 ms 13692 KB
30.txt 305 ms 13692 KB
31.txt 43 ms 13692 KB
32.txt 43 ms 13692 KB
33.txt 43 ms 13692 KB
34.txt 43 ms 13692 KB
35.txt 43 ms 13692 KB
36.txt 43 ms 13692 KB
37.txt 43 ms 13692 KB
38.txt 43 ms 13692 KB
39.txt 43 ms 13692 KB
40.txt 75 ms 13692 KB
41.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB